Big O Notation
Algorithms & Complexity · Coding Fundamentals track
6 min read
In this module
Measuring Growth, Not Speed
How fast is your algorithm? "It takes 3 milliseconds" doesn't really tell you much. That number depends on your hardware, your input, and whatever else is hogging the CPU. We need a way to describe efficiency that is independent of any specific machine.
Big O notation describes how an algorithm's resource usage (usually time or space) grows as the input size n increases. It captures the growth rate: the shape of the curve, not the exact numbers.
The Common Complexities
Here are the most important Big O classes, from fastest to slowest:
O(1) - Constant time. Same cost regardless of input size. Indexing an array, pushing to a stack, hash-table lookup (amortised).
O(log n) - Logarithmic time. Each step kills off a fraction of the remaining work. Binary search is the textbook example. Double the input and you only add one more step.
O(n) - Linear time. You touch each element once. Searching an unsorted list, summing all elements, walking a linked list.
O(n log n) - Linearithmic time. The best you can do with comparison-based sorting. Merge sort and heapsort hit this bound.
O(n^2) - Quadratic time. Every element gets compared with every other element. Bubble sort, selection sort, insertion sort (worst case). Nested loops over the same data.
O(n^3) - Cubic time. Three nested loops over the data. Multiplying two n-by-n matrices the schoolbook way is the usual example.
O(2^n) - Exponential time. Each extra input element doubles the work. Brute-forcing combinatorial problems lives here.
O(n!) - Factorial time. Trying every possible ordering of the input, like checking every route in a brute-force travelling salesman solver. Even n = 20 gives about 2.4 quintillion orderings.
Big O notation describes the upper bound on growth rate. O(n) means the time grows at most linearly with input size. O(n^2) means at most quadratically. Constants and lower-order terms are dropped because they become insignificant as n grows large.
Why We Drop Constants
Big O ignores constant factors. An algorithm that takes 3n steps and one that takes 100n steps are both O(n). Looks sloppy, but it nails the headline fact: both scale linearly. One might be 33 times faster than the other, but they behave the same way as input grows.
Constants depend on hardware (a faster CPU makes everything faster) and on implementation details. Growth rate is the intrinsic characteristic of the algorithm itself.
In practice, though, constants do matter. An O(n) algorithm with a constant of 1,000,000 lags an O(n^2) algorithm for inputs under 1,000,000. Big O tells you about large-scale behaviour. Profiling tells you about actual performance.
Analysing Simple Code
To determine Big O, count how the number of "significant operations" grows with n.
// O(1) - constantfunction get_first(list) { return list[0]}
// O(n) - linearfunction find_max(list) { max = list[0] for i = 1 to length(list) - 1 { if list[i] > max { max = list[i] } } return max}
// O(n^2) - quadraticfunction has_duplicate(list) { for i = 0 to length(list) - 1 { for j = i + 1 to length(list) - 1 { if list[i] == list[j] { return true } } } return false}In find_max, the loop runs n-1 times. Drop the constant and you have O(n).
In has_duplicate, the nested loops compare each pair. Total comparisons come to roughly n*(n-1)/2, which simplifies to O(n^2).
You don't have to take that on trust. This C version counts its own comparisons on lists with no duplicates (the worst case, since nothing ends the search early). Predict the count for n = 1000 first.
Space Complexity
Big O also applies to memory usage. Some algorithms use extra memory proportional to their input:
- O(1) space - uses a fixed amount of extra memory (bubble sort)
- O(n) space - uses memory proportional to input (merge sort needs a temporary array)
- O(n^2) space - rare but possible (storing all pairs)
You'll often hit a time-space tradeoff: spend more memory to save time, or run leaner on memory and pay for it in cycles.
Practical Intuition
For a rough sense of what is practical:
- O(n) with n = 1 billion: takes seconds. Feasible.
- O(n log n) with n = 1 billion: takes tens of seconds. Feasible.
- O(n^2) with n = 1 million: takes minutes to hours. Getting slow.
- O(n^2) with n = 1 billion: takes years. Infeasible.
- O(2^n) with n = 40: about a trillion steps, so minutes. With n = 100: takes longer than the age of the universe.
This is why choosing the right algorithm matters so much. The gap between O(n) and O(n^2) is the gap between "runs instantly" and "never finishes."
Best, Worst, and Average Case
Many algorithms behave differently depending on the input:
- Best case: The most favourable input. Linear search finds the target on the first try: O(1).
- Worst case: The most unfavourable input. Linear search checks every element: O(n).
- Average case: The expected behaviour over random inputs. Linear search checks about n/2 elements: O(n).
Strictly, Big O is just an upper bound, and you can state one for any of these cases. When people quote a single Big O for an algorithm without saying which case, they almost always mean the worst case, because that's the guarantee on offer: "whatever input you throw at me, I won't be slower than this."
Big O has two siblings you'll meet in more formal texts. Omega (Ω) gives a lower bound, "at least this much growth", and Theta (Θ) says both bounds match, so the growth rate is pinned exactly. Merge sort, for example, is Θ(n log n) in every case.