RajScape

Big O notation is the language computer scientists use to describe how the performance of an algorithm scales with the size of the input. It is one of the most fundamental concepts in computer science, and understanding it is essential for evaluating algorithms, making design decisions, and succeeding on the AP CSP and AP CSA exams. In this post, we will demystify Big O notation and show you how to analyze the efficiency of algorithms.

What Is Big O Notation?

Big O notation describes the upper bound of an algorithm's running time as a function of the input size n. It tells us how the running time grows as n increases. Big O notation ignores constant factors and lower-order terms because they become insignificant as n grows large. For example, an algorithm that takes 3n² + 5n + 100 operations is described as O(n²) because the n² term dominates as n becomes large.

Big O notation is not about the exact number of operations. It is about the growth rate. An O(n²) algorithm will always eventually be slower than an O(n) algorithm for large enough inputs, regardless of the constant factors involved. This allows us to compare algorithms at a high level without getting bogged down in implementation details.

Common Big O Complexities

O(1) describes constant time operations. The running time does not depend on the input size. Examples include accessing an array element by index, pushing or popping from a stack, and inserting at the beginning of a LinkedList.

O(log n) describes logarithmic time. The running time grows proportionally to the logarithm of the input size. Binary search is the classic example. Each step cuts the search space in half, so the number of steps grows very slowly even as the input size grows rapidly.

O(n) describes linear time. The running time grows proportionally with the input size. Examples include linear search, iterating through an array, and finding the maximum element in an unsorted array.

O(n log n) describes linearithmic time. This is the efficiency of efficient sorting algorithms like merge sort and heapsort. It is faster than O(n²) but slower than O(n).

O(n²) describes quadratic time. The running time grows proportionally to the square of the input size. Examples include bubble sort, selection sort, and checking every pair of elements in an array. Quadratic algorithms become impractical for large inputs.

O(2ⁿ) describes exponential time. The running time doubles with each additional input element. This is typical of algorithms that try every possible combination, such as certain recursive algorithms that solve problems by brute force. Exponential algorithms are only practical for very small inputs.

Analyzing Loops

The most common way to determine the time complexity of an algorithm is to analyze its loops. A single loop that iterates n times is O(n). A nested loop where both loops iterate n times is O(n²). A loop that iterates log n times is O(log n). When analyzing nested loops, you multiply the complexities: an outer loop of O(n) with an inner loop of O(n) gives O(n × n) = O(n²).

When analyzing a loop, pay attention to how the loop variable changes. A loop that increments by 1 each time (for (int i = 0; i < n; i++)) runs n times, giving O(n). A loop that doubles each time (while (i < n) i *= 2) runs log n times, giving O(log n). A loop that decrements by a fixed amount each time also runs n divided by that amount times, which is still O(n).

Best, Worst, and Average Case

Big O notation can describe the best case, worst case, or average case performance of an algorithm. For linear search, the best case is O(1) (the target is the first element), the worst case is O(n) (the target is the last element or not in the list), and the average case is O(n/2) = O(n).

When people refer to the Big O of an algorithm without specifying best, worst, or average case, they usually mean the worst case. This is because the worst case provides a guaranteed upper bound on the running time. However, in some contexts, average case analysis is more meaningful, especially for algorithms like hash table lookups where the average case is much more representative of typical performance.

Space Complexity

Big O notation can also describe the space complexity of an algorithm, which is how much additional memory the algorithm uses as a function of the input size. An algorithm that uses a fixed amount of additional memory regardless of input size is O(1) in space. An algorithm that creates a new array of the same size as the input is O(n) in space. An algorithm that creates a 2D array of size n×n is O(n²) in space.

Understanding space complexity is important because there is often a trade-off between time and space. An algorithm that uses more memory may run faster, while an algorithm that uses less memory may run slower. Choosing the right algorithm requires considering both time and space constraints.

Big O on the AP Exams