The common growth rates
O(1) to O(n!) — what each looks like in code and how many steps it means at real input sizes.
Big idea
Almost every algorithm you'll meet falls into one of about eight growth rates. Knowing roughly how many steps each one means at n = 10⁵ tells you instantly which solutions are viable and which are hopeless.
The ladder
From fastest to slowest:
| Big-O | Name | Typical shape in code | Steps at n = 10⁵ |
|---|---|---|---|
| O(1) | constant | array index, hash lookup | 1 |
| O(log n) | logarithmic | halve the search space each step | ~17 |
| O(n) | linear | one pass over the input | 100,000 |
| O(n log n) | linearithmic | good sorting; n items × log n work each | ~1.7 million |
| O(n²) | quadratic | every pair of items (nested loops) | 10 billion |
| O(n³) | cubic | every triple | 10¹⁵ |
| O(2ⁿ) | exponential | every subset | more than atoms in the universe |
| O(n!) | factorial | every ordering | even more |
A typical judge does around 10⁸ simple steps per second. So at n = 10⁵, O(n log n) finishes in a few milliseconds, while O(n²) needs about 100 seconds — a time-out.
Watch it
What makes a log n
A logarithm counts how many times you can halve n before reaching 1. log₂ of 1,000 is about 10; of 1,000,000 about 20; of 1,000,000,000 about 30. Whenever an algorithm throws away half of what's left each step — binary search, a balanced tree walk — it's O(log n).
def halvings(n):
steps = 0
while n > 1:
n //= 2 # half the problem is gone
steps += 1
return steps # about log2(n)That's why O(log n) feels like O(1) in practice: going from a thousand to a billion items only triples the work.
What makes n log n
n log n usually means "do O(log n) work for each of n items" or "split in half log n times, doing O(n) work per level". Merge sort is the second kind: there are log n levels of splitting, and each level touches all n items once.
Exponential and factorial
Generating every subset of n items means 2ⁿ results: 2¹⁰ = 1,024 is fine, 2³⁰ ≈ a billion is already too slow, 2⁶⁰ is impossible. Every ordering of n items is n!: 10! = 3.6 million, but 15! = 1.3 trillion. These show up in backtracking, and are only acceptable when n is tiny (roughly n ≤ 20 for 2ⁿ, n ≤ 10 for n!).
Comparing two solutions
If one approach is O(n²) and another is O(n log n), the second wins for any input big enough to matter — even if its constant is 50× worse. At n = 10⁵, n² is 10¹⁰ while 50 × n log n is under 10⁸.
Quick check
Order these growth rates from fastest (fewest steps) to slowest.
Binary search on 1,000,000 sorted items takes about how many comparisons in the worst case?
With a budget of about 10⁸ steps per second, how long would an O(n²) solution take on n = 10⁵?