The Common Growth Rates

A ladder of growth

A handful of growth rates cover most algorithms you will meet, from fastest-growing work to slowest: O(1) constant (array index, hash lookup on average), O(log n) logarithmic (binary search, balanced tree operations), O(√n) (trial division up to the square root), O(n) linear (one pass), O(n log n) linearithmic (efficient sorting such as merge sort), O(n²) quadratic (comparing all pairs), O(n³) cubic (naive matrix multiplication, triple loops), O(2ⁿ) exponential (all subsets), and O(n!) factorial (all orderings). The gaps are enormous. With n = 1,000,000, log₂ n is about 20, n log₂ n about 20 million, and n² a trillion. Exponential and factorial algorithms are usable only for tiny n: 2³⁰ is about a billion, and 20! is about 2.4 × 10¹⁸. A useful habit is to compute these numbers for your actual input sizes before choosing an approach.

Growth rates at a glance

Approximate number of basic steps for each n (log base 2).

n            log n   n log n         n^2            2^n
-----------  ------  --------------  -------------  -------------------
10           ~3      ~33             100            1,024
100          ~7      ~664            10,000         ~1.3 x 10^30
1,000        ~10     ~10,000         1,000,000      astronomically large
1,000,000    ~20     ~20,000,000     10^12          -

ordering: 1 < log n < sqrt(n) < n < n log n < n^2 < n^3 < 2^n < n!

log n is tiny

Students often treat O(log n) as "a bit less than n". It is far smaller: for a billion items, log₂ n is only about 30. That is why binary search and balanced trees scale so well.

Quick check: Which growth rate is the smallest for large n?

• O(n)
• O(n log n)
• O(log n)
• O(√n)