Growth of Complexity Functions — previous-year questions

The capstone of the analysis unit: previous-year questions that ask you to arrange functions in increasing order of growth or pick the odd one out. These reward technique over memory.

The three-step routine

1. Bucket first. Sort options into constant / polylog / polynomial / n log n-type / exponential / factorial buckets — the ladder from the previous lesson resolves across-bucket order instantly.
2. Within a bucket, take logs. f < g ⇔ log f < log g for large n, and logs turn exponent battles into products you can eyeball.
3. Normalise stubborn pairs with a^log_b n = n^log_b a. Seeing 3^log₂ n as n^log₂ 3 = n^1.585 places it immediately between n and n².

Classic traps from past papers

• n^log n is not polynomial (the exponent grows) — it sits between every polynomial and every true exponential.
• 2^√n beats every polynomial but loses to 2ⁿ — “sub-exponential” lives in the gap.
• n! vs nⁿ vs 2ⁿ: always 2ⁿ < n! < nⁿ; log-Stirling proves it in one line.
• Functions equal up to constants (log₂ n vs ln n, n + log n vs n) must be grouped as Θ-equal, not ordered — questions include such pairs to catch over-ordering.

Exam discipline

• Never decide from n = 2 or n = 10 — small-n tables invert the true asymptotic order surprisingly often; trust limits and logs.
• In multi-function orderings, verifying just the adjacent pairs of your proposed order is enough — and much faster than all-pairs checking.

Solve each question in the video before the reveal, then mark the lesson complete — this closes the analysis toolkit the rest of the course builds on.