Time Complexity & the Class P

the ladder of growth rates

Growth rates are not a smooth dial; they come in recognisable rungs, and learning the ladder gives you instant intuition for whether an algorithm scales. From bottom (fastest, best) to top (slowest, worst), the common rungs are: constant O(1), logarithmic O(log n), linear O(n), n-log-n O(n log n), quadratic O(n^2), cubic O(n^3), general polynomial O(n^k), exponential O(2^n), and factorial O(n!). Each rung is dramatically slower than the one below as n grows; the jump from polynomial to exponential is the canyon that divides 'tractable' from 'intractable'.

A feel for the numbers makes the ladder vivid. Logarithmic means doubling the input adds only a constant amount of work, like binary search halving a phone book. Linear means doubling the input doubles the work. Quadratic means doubling the input quadruples it. But exponential is a different beast: each extra element of input doubles the total work, so going from n = 40 to n = 41 doubles a 2^40 (about a trillion) step computation. Factorial is worse still: 10! is about 3.6 million, but 20! is about 2.4 times 10^18, the realm of checking every ordering of a list. Polynomials of any fixed degree stay on the gentle side of the canyon; anything 2^n or above falls off the cliff.

This ladder is why complexity theory draws its great dividing line between polynomial and exponential, and why the class P (polynomial time) is the standard stand-in for efficient. It also explains common algorithm-design goals: turning a quadratic algorithm into an n-log-n one is a real win on big data, and turning an exponential brute-force search into any polynomial method is often the difference between impossible and routine. Keep the ladder in your head and most efficiency questions answer themselves at a glance.

For n = 50, the rungs differ wildly: log n is about 6, n is 50, n log n is about 300, n^2 is 2500, n^3 is 125000 (all easy), but 2^n is about 10^15 (a quadrillion) and n! is about 3 times 10^64. A computer doing a billion steps a second finishes the polynomial ones instantly and would never finish the factorial one.

At n = 50 the polynomial rungs are trivial while exponential and factorial are hopeless: the canyon between them is the whole point.

The crucial boundary is polynomial versus exponential, not between adjacent polynomial rungs; an O(n^3) algorithm and an O(n) one are both tractable, but O(2^n) is a different world.

Also called
growth hierarchycommon complexity classes by growthcomplexity ladder成長率階層