The ladder of growth rates

Constant, logarithmic, linear, n log n, polynomial, exponential and factorial, plus the two odd ones that turn up in real analysis.

Almost every running time you meet falls into a short list of shapes, and knowing that list by heart is what lets you glance at an algorithm and know whether it is worth writing. The differences between the shapes are much larger than most people expect, so it is worth watching them once at full scale.

The following table prints, for a few input sizes, what each shape evaluates to. Read the last two columns carefully.

At $n = 60$ the quadratic column is 3600, which any machine finishes instantly. The $2^n$ column is about $1.15 \times 10^{18}$, which at a billion operations a second takes about 36 years. The factorial column is about $8 \times 10^{81}$, which is a number of the same order as the count of atoms in the observable universe.

The classes, in order

A polynomial cost is one bounded by $n^k$ for some fixed $k$: linear, quadratic and cubic are all polynomial. An exponential cost has $n$ in the exponent, like $2^n$ or $3^n$. Every polynomial is eventually beaten by every exponential, however extreme the exponents look: $n^{100}$ is smaller than $1.01^n$ for large enough $n$, though that $n$ is astronomically large.

Why the base of a logarithm is not written

A logarithm answers the question: to what power must the base be raised to reach this number? Since $2^{10} = 1024$, $\log_2 1024 = 10$. Changing base only multiplies by a fixed number, because $\log_b n = \log_2 n / \log_2 b$, and $\log_2 b$ does not depend on $n$.

So $\log_{10} n$ and $\log_2 n$ differ by the constant factor $\log_2 10 \approx 3.32$, and constants vanish inside Theta. That is why $\Theta(\log n)$ is written with no base at all. The one place the base does matter is inside an exponent: $2^n$ and $3^n$ are genuinely different, since their ratio $(3/2)^n$ grows without bound.

Harmonic sums

One pattern turns up so often that its answer is worth knowing outright. A loop whose inner work shrinks as $n/1$, then $n/2$, then $n/3$, and so on, adds up to $n$ times the harmonic number $H_n = 1 + 1/2 + 1/3 + \cdots + 1/n$.

The sum of a million reciprocals is only about 14.39, and it stays about $\ln n$ plus a fixed number close to 0.5772. So $H_n = \Theta(\log n)$, and a loop costing $n/1 + n/2 + \cdots + n/n = n H_n$ costs $\Theta(n \log n)$, not $\Theta(n^2)$ as the first term alone might suggest.

The iterated logarithm

The iterated logarithm, written $\log^* n$, counts how many times you must take the logarithm before the result drops to 1 or below. It grows so slowly that for every input any real computer will ever hold, its value is at most 5.

Put a million items through each of those two shapes and count. A linear pass is $10^6$ operations, which at a hundred million operations a second is about a hundredth of a second. A quadratic one is $(10^6)^2 = 10^{12}$ operations, which at the same rate is $10^4$ seconds, or a little under three hours.