Growth of Complexity Functions

Once notation is solid, the practical skill is ordering functions by growth rate — a direct question type in itself and the backbone of every “tightest bound” pick.

The standard ladder (slowest → fastest)

1 < log log n < log n < (log n)ᵏ < √n < n < n log n < n² < n³ < nᵏ < 2ⁿ < 3ⁿ < n! < nⁿ

Any polynomial beats any polylogarithm; any exponential beats any polynomial — no matter the constants or exponents involved.

Comparison techniques

• Take logs of both. Comparing n^√n with (√n)^n? Their logs are √n·log n vs (n/2)·log n — the second wins. Taking logs preserves order for large n.
• Take the limit of the ratio: 0 means the numerator grows slower, ∞ means faster, a constant means Θ of each other. L’Hôpital is fair game.
• Normalize exponents: rewrite everything as 2^(…) and compare the exponents — 4^log n = n², 2^(2 log n) = n², so they tie.

Special values worth memorising

• log(n!) = Θ(n log n); n! ≈ (n/e)ⁿ√(2πn) (Stirling).
• 2^log₂ n = n, and in general a^log_b n = n^log_b a — the identity that cracks most “weird exponent” questions.
• (log n)^100 = o(n^0.01) — polylogs lose to ANY positive power of n.

Why this matters beyond exams

The ladder is the intuition for algorithm choice: an O(n log n) sort is usable at n = 10⁸; an O(n²) one is not. Placement coding rounds enforce it via time limits — roughly, 10⁸ basic operations per second is the budget to plan against.