Growth-rate race · log n vs n² vs 2ⁿ

Complexity is about how time grows with input size, not about absolute speed. The race here puts six canonical growth rates side by side so you can watch which ones stay manageable and which explode.

Suppose you have an algorithm that runs in 10⁻⁹ × T(n) seconds (one nanosecond per operation). How big a problem can you solve in one second of CPU time?

• log n algorithm: n ≈ 2^10⁹. Astronomical. Logarithmic algorithms scale trivially.
• linear (n): n = 10⁹. A billion items in a second.
• n log n: n ≈ 4 × 10⁷. Forty million items.
• n²: n ≈ 3 × 10⁴. Thirty thousand items.
• n³: n = 1000. A thousand items.
• 2ⁿ: n ≈ 30. Thirty items. Thirty.

This is why P is the working definition of "feasible" — polynomial-time algorithms scale; exponential-time ones do not.

• Constants matter in practice but not in P. A 10¹⁰⁰·n algorithm is in P. In the real world it's useless. But P is a mathematical category, not an engineering claim — and the gap between "in P" and "fast in practice" is usually small for natural problems.
• n log n is below n². Easy to forget under pressure. n log n grows much slower than n²; log n grows much slower than n.
• 2ⁿ is not "n times worse than n." It's doubled per step. The intuition "exponential just means a lot" misses that one extra bit of input doubles the work.
• Pseudo-polynomial isn't polynomial. Algorithms like SUBSET-SUM's DP run in O(n·S) where S is the numeric value of the input — but S itself can be exponential in the number of bits. Polynomial means polynomial in bit length, not in the value.

• Q1. Why use a log scale on the y-axis?
  Because 2ⁿ at n=40 is ~10¹² while n² is 1600. A linear scale would flatten all polynomials into a single horizontal line at the bottom, hiding the polynomial-vs-polynomial differences. The log scale makes constant-factor differences look like vertical translations, which is exactly how Big-O treats them.
• Q2. Where does 2ⁿ overtake n³?
  Around n = 10. At n = 10, both are 1024 vs 1000. After that, 2ⁿ doubles each step while n³ grows by a factor (n+1)³/n³ ≈ 1 + 3/n that shrinks toward 1. Exponential wins decisively.
• Q3. Why is polynomial vs exponential the "right" boundary?
  The Cobham–Edmonds thesis: polynomial time is closed under composition (a polynomial in a polynomial is a polynomial), robust across reasonable machine models, and matches empirical experience with feasible algorithms. Exponential time has none of those properties — composition explodes, model choice matters more, and exponential algorithms rarely scale to interesting input sizes.
• Q4. Is n¹⁰⁰ really feasible?
  In theory it's in P. In practice, even n = 2 gives 2¹⁰⁰ steps — completely infeasible. The Cobham–Edmonds thesis is empirical: most natural problems in P turn out to have algorithms with small exponents. The famous exception is interior-point methods for LP (originally n³·⁵, now n^(2+ε)).

Sipser: §7.1 (Big-O), §7.2 (P). Lecture notes: Module 4 slide 1 has the same race; slide 2 covers Big-O formally. Companion problems: P18 (single-tape 0ⁿ1ⁿ — concrete O(n²) example), P20 (Big-O classifier), P24 (P showcase — natural P algorithms).