The common growth rates, ordered from slowest-growing (best as n scales) to fastest-growing (worst), are:
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Each step is a categorical jump in how the algorithm scales — not a constant-factor difference. Knowing this ordering cold lets you sanity-check any complexity claim instantly.
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| O(1) constant | 1 | 1 | 1 | HashMap.get, array index, stack push |
| O(log n) logarithmic | ~20 | ~20 | ~20 | binary search, balanced-tree ops (n = 10⁶) |
| O(n) linear | 10⁶ | 10⁶ | 10⁶ | single pass, linear scan |
| O(n log n) linearithmic | ~2×10⁷ | ~2×10⁷ | ~2×10⁷ | MergeSort, Timsort, heap sort |
| O(n²) quadratic | 10¹² | 10¹² | 10¹² | nested loops, bubble/insertion sort |
| O(2ⁿ) exponential | intractable | intractable | intractable | naive subsets, brute-force recursion |
| O(n!) factorial | intractable | intractable | intractable | permutations, brute-force TSP |
(Counts above are illustrative operation counts at n = 10⁶, except the bottom two which are astronomically large.)
The intuition behind the order
- O(1) — cost independent of
n. The gold standard. - O(log n) — each step halves the problem. Grows so slowly it is nearly constant:
n = 10⁹takes only ~30 steps. - O(n) — you must at least look at every element. The floor for any problem that reads all its input.
- O(n log n) —
nwork repeated acrosslog nlevels. The practical limit for comparison sorting (Ω(n log n) lower bound). - O(n²) — every element paired with every other. Fine for small
n, lethal past ~10⁴. - O(2ⁿ) — one branch per element; the search space doubles with each added element. Tractable only for tiny
n(≈20–25). - O(n!) — every ordering. Falls apart past
n ≈ 11.
The dividing line
Everything up through O(n log n) is polynomial and practical. O(2ⁿ) and O(n!) are exponential — you can solve them only for tiny inputs, or you must find a polynomial reformulation (often dynamic programming) or accept an approximation.