# The Common Growth Rates — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/f-growth

> Order the standard growth rates and estimate their size for real inputs.

## 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).

```text
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.

**Quiz:** Which growth rate is the smallest for large n?

- [ ] O(n)
- [ ] O(n log n)
- [x] O(log n)
- [ ] O(√n)

*Answer:* O(log n). Logarithmic growth is slower than any polynomial power of n, including √n.