Day 82 — Growth classes

Updated

July 30, 2026

Day 82 — Growth classes and dominance

Stage VIII · concept day
Goal: Rank standard growth families; use Stirling’s approximation for \(n!\); prove polynomial vs exponential dominance; compare logs, polylog, \(n^k\), \(n\log n\), \(c^n\), \(n!\), double exponential.

Why this matters

Algorithm design is often a fight to move a cost down the growth ladder. Knowing that \(n^{100}=o(2^n)\) and that \(n!\) outgrows \(c^n\) prevents both panic and false comfort. Stirling connects factorials to continuous approximations used in counting and information theory literacy.

Note

No labs. Comparisons, limit arguments, and ranking tables only.

Theory

Standard ladder (slowest to fastest, schematic)

For large \(n\), with constants \(c>1\) and fixed \(k\ge 1\): \[ 1 \prec \log n \prec \mathrm{polylog} \prec n^{\varepsilon} \prec n^k \prec n^k\log n \prec n^{k+\delta} \prec c^n \prec n! \prec n^n \prec 2^{2^n} \] in the sense of \(f\prec g\) meaning \(f=o(g)\). More carefully, fix representatives:

Class Representative Notes
Constant \(1\) \(O(1)\) algorithms
Logarithmic \(\log n\) binary search
Polylog \((\log n)^k\) any fixed \(k\)
Fractional power \(n^{\varepsilon}\) (\(\varepsilon>0\) small) beats every polylog
Polynomial \(n^k\) \(k\) fixed
Linearithmic \(n\log n\) good sorts
Higher poly \(n^{k+\delta}\)
Exponential \(c^n\) (\(c>1\)) subset enum, etc.
Factorial \(n!\) permutations
Super-exp \(n^n\), \(2^{2^n}\)

Important: \(n^{100}\) is still polynomial; \(1.001^n\) is still exponential and eventually larger than \(n^{100}\).

Logarithms

For any bases \(a,b>1\), \(\log_a n=\Theta(\log_b n)\) because \(\log_a n=\log_b n/\log_b a\). Changing log base never changes asymptotic class among logs.

Polylog vs power: for any \(k\) and any \(\varepsilon>0\), \[ (\log n)^k = o(n^{\varepsilon}). \] Proof idea: set \(n=e^t\), reduce to \(t^k e^{-\varepsilon t}\to 0\).

Polynomials

If \(k<\ell\) then \(n^k=o(n^\ell)\). A polynomial \(a_d n^d+\cdots+a_0\) with \(a_d\neq 0\) is \(\Theta(n^d)\).

\(n\log n\) vs \(n^{1+\varepsilon}\)

\(n\log n=o(n^{1+\varepsilon})\) for every \(\varepsilon>0\), but \(n\log n=\omega(n)\). So \(n\log n\) sits strictly between linear and any higher fixed power \(n^{1+\varepsilon}\).

Exponential vs polynomial

Theorem. For any fixed \(k\) and any \(c>1\), \[ n^k = o(c^n). \] Proof sketch. Ratio \(r(n)=n^k/c^n\). Then \(r(n+1)/r(n)=((n+1)/n)^k / c \to 1/c<1\). Eventually the ratio is \(<\rho<1\), so \(r(n)\) decays geometrically → \(0\).

Corollary. Every polynomial-time bound is \(o(\text{exponential})\) for any base \(>1\).

Stirling’s approximation

Theorem (Stirling, use form). \[ n! \sim \sqrt{2\pi n}\,\Bigl(\frac{n}{e}\Bigr)^n, \] meaning the ratio of the two sides tends to \(1\) as \(n\to\infty\).

Consequences.

  1. \(\log(n!)=\Theta(n\log n)\) (take log of Stirling).
  2. \(n!=\omega(c^n)\) for any fixed \(c\): because \((n/e)^n\) already dominates \(c^n\) after polynomial factors.
  3. \(\binom{2n}{n}\sim 4^n/\sqrt{\pi n}\) (central binomial literacy).

Use without proof of Stirling; apply it.

Factorial vs exponential

Proposition. \(c^n=o(n!)\) for any fixed \(c\).
Proof sketch. \(n!/c^n = (1/c)(2/c)\cdots(n/c)\); for \(n>2c\) terms exceed \(2\), and the product → \(\infty\).

Double exponential and towers

\(2^{2^n}\) grows vastly faster than \(2^n\) or \(n!\). These appear in some logic/automaton bounds — awareness for “how bad bad can be.”

Comparing via limits

To rank \(f\) and \(g\), compute \(\lim f/g\) in \([0,\infty]\) when possible (L’Hôpital, Stirling, ratio test style for sequences).

Polynomial hierarchy of exponents

Within polynomials, only the degree matters for \(\Theta\) class of a single monomial. For algorithms, reducing degree (\(n^3\to n^2\)) is huge even though both are “poly.”

Worked examples

Example 1 — Rank.
Order: \((\log n)^5\), \(n\), \(n\log n\), \(n^2\), \(2^n\), \(n!\).
Check pairwise with limits if unsure.

Example 2 — \(n^{100}\) vs \(1.01^n\).
\(n^{100}/(1.01)^n\to 0\), so \(n^{100}=o(1.01^n)\).

Example 3 — Stirling for \(\log(n!)\).
\(\log(n!)\approx n\log n - n + \frac12\log(2\pi n)=\Theta(n\log n)\).

Example 4 — \(n!\) vs \(2^n\).
\(2^n/n!\to 0\), so \(2^n=o(n!)\).

Example 5 — Polylog vs root.
\((\log n)^{100}/n^{0.001}\to 0\).

Example 6 — Same class.
\(5n^3+100n^2+7=\Theta(n^3)\), not \(\Theta(n^2)\).

Example 7 — \(n^n\) vs \(n!\).
\(n^n/n! = n\cdot n/\ 2\cdot \ldots\) huge; \(n!=o(n^n)\). Also \(n^n=e^{n\ln n}\) vs Stirling.

Example 8 — Binary vs natural log.
\(\log_2 n=\ln n/\ln 2=\Theta(\ln n)\).

Example 9 — Two exponentials.
\(2^n=o(3^n)\) because \((2/3)^n\to 0\).

Example 10 — Algorithm moral.
An \(O(n^2)\) algorithm beats \(O(2^n)\) for large \(n\) regardless of constant factors in typical ranges — but constants matter when comparing \(n^2\) vs \(1000 n\log n\) at moderate \(n\). Asymptotics are eventual.

Exercises

A. Ranking

  1. Sort by increasing growth: \(2^n\), \(n^3\), \(n!\), \(\log n\), \(n\log n\), \(n^n\), \(1\).
  2. Insert \((\log n)^n\) carefully — is it exponential-ish? (Write \(e^{n\ln\log n}\).)
  3. Compare \(n^{\log n}\) and \((\log n)^n\).
  4. True/false: \(n^{1000}=O(2^n)\).
  5. True/false: \(2^{n}=O(n!)\).

B. Limit proofs

  1. Prove \((\log n)^3=o(\sqrt{n})\).
  2. Prove \(n^5=o(1.1^n)\).
  3. Prove \(3^n=o(n!)\).
  4. Prove \(n\log n=o(n^{1.1})\).
  5. Prove \(2^{n}=o(2^{2n})\) and \(2^{2n}\neq O(2^{n})\).
  6. Using Stirling, show \(\log_2(n!)\sim n\log_2 n\).
  7. Using Stirling, show \(\binom{2n}{n}=\Theta(4^n/\sqrt{n})\).

C. Polynomials and combinations

  1. Find \(\Theta\) class of \(3n^4+2n^2\log n+100n\).
  2. Find \(\Theta\) class of \((n+1)^5-(n-1)^5\) (expand or factor).
  3. Compare \(\sum_{k=1}^n k=\Theta(n^2)\) with \(\sum_{k=1}^n k^2=\Theta(n^3)\) (Day 83 preview).
  4. Show \(\max(n^2,100n)=\Theta(n^2)\).

D. Applied literacy

  1. Why is “exponential time” scarier than “polynomial with large degree” for asymptotic \(n\to\infty\), yet degree still matters in practice?
  2. Sorting lower bound culture: comparison sorts need \(\Omega(n\log n)\) worst-case in decision-tree model — where does this sit on the ladder?
  3. If a crypto attack is \(2^{64}\) steps and another is \(2^{128}\), how many times harder is the second in pure counting terms?
  4. Birthday bound \(2^{b/2}\) vs brute force \(2^b\) — express both on the exponential ladder in \(b\).

E. Stretch

  1. Prove \(n!=o(n^n)\).
  2. Show \(2^{2^n}\) grows faster than \(2^{n!}\) or compare carefully for large \(n\).
  3. For \(a_n=(1+1/n)^n\), recall \(a_n\to e\); relate to Stirling’s \(e^{-n}\) factor.
  4. Rank \(n^{\sqrt{n}}\), \(2^{n}\), \(e^{n}\), \((\log n)^{n}\).
  5. Prove that for any fixed \(k\), \(\sum_{j=0}^k n^j=\Theta(n^k)\).

Deep dive — polynomial vs exponential proof written out

Fix \(k\in\mathbb{N}\), \(c>1\). Let \(r_n=n^k/c^n\). Then \[ \frac{r_{n+1}}{r_n}=\Bigl(1+\frac{1}{n}\Bigr)^k\cdot\frac{1}{c}. \] Choose \(N\) so that for \(n\ge N\), \((1+1/n)^k\le (1+c)/2\), hence \(r_{n+1}/r_n\le \rho\) with \(\rho=(1+c)/(2c)<1\).
Then for \(m\ge 0\), \(r_{N+m}\le r_N\rho^m\to 0\). Thus \(r_n\to 0\), i.e. \(n^k=o(c^n)\).

Deep dive — Stirling applications card

Quantity Stirling implies
\(n!\) \(\sim\sqrt{2\pi n}(n/e)^n\)
\(\ln n!\) \(=n\ln n-n+O(\ln n)\)
\(\binom{2n}{n}\) \(\sim 4^n/\sqrt{\pi n}\)
\(n!/c^n\) \(\to\infty\) any fixed \(c\)

Hand use: replace \(n!\) by \((n/e)^n\) for rough log-scale comparisons; keep \(\sqrt{2\pi n}\) when ratios → 1 matter.

Additional worked examples

Example 11 — Rank with limits.
\(f=n\log n\), \(g=n^{1.1}\): \(f/g=(\log n)/n^{0.1}\to 0\) ⇒ \(f=o(g)\).

Example 12 — Two factorials.
\((2n)!/(n!)^2=\binom{2n}{n}\sim 4^n/\sqrt{\pi n}\) grows exponentially in \(n\).

Example 13 — \(n^n\) vs \(c^{n}\).
\(n^n/c^n=(n/c)^n\to\infty\).

Example 14 — Log tower culture.
\(\log\log n\) grows slower than \(\log n\); still \(\omega(1)\).

Example 15 — Algorithm menu.
Binary search \(\Theta(\log n)\); efficient sort \(\Theta(n\log n)\); naive subset enum \(\Theta(2^n)\); all permutations \(\Theta(n!)\).

More exercises

  1. Prove \(2^n=o(n!)\) by writing \(n!/2^n=\prod_{j=1}^n(j/2)\) and bounding.
  2. Compare \(n^{\log n}\) and \((\log n)^n\) via logarithms.
  3. Show \(H_n=\Theta(\log n)\) implies coupon collector \(nH_n=\Theta(n\log n)\) (Day 87 link).
  4. Where does \(n^3/\log n\) sit relative to \(n^3\) and \(n^{2.9}\)?
  5. Using Stirling, estimate \(\log_2(100!)\) approximately.
  6. Prove \(a^n=o(b^n)\) if \(1\le a<b\).
  7. CS: why is \(O(n\log n)\) sorting “feasible” for \(n=10^7\) while \(O(n^2)\) hurts — order-of-magnitude discussion.

Selected mini-solutions

  1. True: \(n^{1000}=o(2^n)\subset O(2^n)\).
  2. True: \(2^n=o(n!)\).
  3. Set \(n=e^t\): \(t^3 e^{-t/2}\to 0\).
  4. \(\log(n!)=n\log n-n+\frac12\log(2\pi n)+o(1)\).

Common pitfalls

Pitfall Fix
Thinking \(n^{100}\) is “basically exponential” Still \(o(c^n)\)
Ignoring base of exponential \(2^n=o(3^n)\)
Confusing \(n\log n\) with \(n^2\) Different classes
Applying Stirling equality as identity for small \(n\) Asymptotic \(\sim\)
Ranking at \(n=10\) only Asymptotics are eventual
Forgetting polylog loses to every positive power \((\log n)^k=o(n^\varepsilon)\)

Study notes — growth ladder (commit to memory)

\[ 1 \prec \log n \prec (\log n)^k \prec n^{\varepsilon} \prec n^k \prec n\log n \prec n^{k+\delta} \prec c^n \prec n! \prec n^n \prec 2^{2^n} \]

Stirling: \(n!\sim\sqrt{2\pi n}(n/e)^n\) ⇒ \(\log(n!)=\Theta(n\log n)\).
Poly vs exp: \(n^k=o(c^n)\) for any fixed \(k\), any \(c>1\).

Synthesis — growth ranking workout

S1. Sort: \((\log n)^3\), \(n^{0.1}\), \(n\), \(n\log n\), \(n^2\), \(2^n\), \(n!\), \(n^n\).

S2. Prove \(n^3=o(1.5^n)\) with the ratio argument.

S3. Prove \(3^n=o(n!)\).

S4. Use Stirling to show \(\log_2(n!)\sim n\log_2 n\).

S5. Compare \(2^{n}\) and \(2^{2n}\); compare \(n!\) and \((n/2)^{n/2}\).

S6. Where does \(n/\log n\) sit vs \(n\) and \(\sqrt{n}\)?

S7. Algorithm menu: match binary search / mergesort / subset enum / perm enum to classes.

S8. Why \(n^{100}\) loses to \(1.01^n\) eventually — one careful paragraph.

Checkpoint

  • Can write the standard growth ladder
  • Can prove \(n^k=o(c^n)\) sketch
  • Can use Stirling to get \(\log(n!)=\Theta(n\log n)\)
  • Can rank \(n\log n\), poly, exp, factorial
  • Exercises A–C done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — polylog loses to every positive power (full)

Theorem. For fixed \(k\ge 1\) and \(\varepsilon>0\), \((\log n)^k=o(n^{\varepsilon})\).

Proof. Set \(n=e^{t}\) with \(t\to\infty\) (equivalently \(t=\ln n\)). Then \[ \frac{(\log n)^k}{n^{\varepsilon}}=\frac{(t/\ln b)^k}{e^{\varepsilon t}}\to 0 \] for any log base \(b>1\), because exponential decay beats polynomial growth in \(t\). (If \(\log\) is \(\log_2\), only constant factors change.)

Corollary. \(n(\log n)^k=o(n^{1+\varepsilon})\) for every \(\varepsilon>0\).

Deeper theory — factorial beats exponential (full product)

Theorem. For fixed \(c>1\), \(c^n=o(n!)\).

Proof. Write \[ \frac{n!}{c^n}=\prod_{j=1}^n\frac{j}{c}. \] Choose integer \(N>2c\). For \(n>N\), \[ \frac{n!}{c^n}=\Bigl(\prod_{j=1}^{N}\frac{j}{c}\Bigr)\cdot\prod_{j=N+1}^n\frac{j}{c}\ge C_N\cdot 2^{n-N} \] because each factor \(j/c>2\) for \(j>N\). Hence \(n!/c^n\to\infty\).

Worked examples — ranking with limits

Example 16 — Place \(n/\log n\).
\(n/\log n=\omega(\sqrt{n})\) because \((n/\log n)/\sqrt{n}=\sqrt{n}/\log n\to\infty\).
\(n/\log n=o(n)\) because \(1/\log n\to 0\). So \(\sqrt{n}\prec n/\log n\prec n\).

Example 17 — \(n^{\log n}\) vs \((\log n)^n\).
Take \(\ln\): \(\ln(n^{\log n})=\log n\cdot\ln n\) (careful with log base).
\(\ln((\log n)^n)=n\ln\log n\).
For large \(n\), \(n\ln\log n\) grows faster than \((\log n)(\ln n)\), so \((\log n)^n\) is larger. (Work in a fixed base throughout.)

Example 18 — Stirling for \(\binom{2n}{n}\).
\(\binom{2n}{n}=(2n)!/(n!)^2\sim \frac{\sqrt{4\pi n}(2n/e)^{2n}}{2\pi n(n/e)^{2n}}=4^n/\sqrt{\pi n}\).

Example 19 — Algorithm ladder map.
| Task | Growth | |——|——–| | Binary search | \(\Theta(\log n)\) | | Linear scan | \(\Theta(n)\) | | Heapsort comparisons | \(\Theta(n\log n)\) | | Naive all subsets | \(\Theta(2^n)\) | | All permutations | \(\Theta(n!)\) |

Extra exercises — dominance drills

  1. Prove \((\log n)^5=o(n^{0.01})\).
  2. Prove \(n^7=o(1.01^n)\) with ratio \(r_{n+1}/r_n\).
  3. Rank: \(2^{n}\), \(n^{n/2}\), \(n!\), \(3^{n}\).
  4. Show \(H_n=\Theta(\log n)\) implies \(nH_n=\Theta(n\log n)\).
  5. Using Stirling, estimate \(\log_2(50!)\) roughly.
  6. Compare \(n^3/\log n\) to \(n^{2.9}\) and \(n^3\).
  7. True/false with proof: \(2^{n+1}=\Theta(2^n)\) but \(2^{2n}\neq\Theta(2^n)\).
  8. CS: for \(n=10^6\), compare rough operation counts \(n\log_2 n\) vs \(n^2\) (order of magnitude).

Mini-solutions (selected)

  1. \(r_n=n^7/(1.01)^n\), \(r_{n+1}/r_n=((n+1)/n)^7/1.01\to 1/1.01<1\).
  2. First: factor \(2\). Second: \(2^{2n}/2^n=2^n\to\infty\).
  3. \(n\log_2 n\approx 10^6\cdot 20=2\cdot 10^7\); \(n^2=10^{12}\) — about \(5\cdot 10^4\) times larger.

Closing synthesis card

\[ 1\prec\log n\prec(\log n)^k\prec n^\varepsilon\prec n^k\prec n\log n\prec n^{k+\delta}\prec c^n\prec n!\prec n^n\prec 2^{2^n} \]

Three proofs to own: poly vs exp ratio; exp vs factorial product; Stirling ⇒ \(\log(n!)=\Theta(n\log n)\).

Tomorrow

Day 83 — Loops to sums to bounds; amortized idea.