Day 28 — Asymptotic Notation & Complexity Analysis

Updated

July 30, 2025

Day 28 — Asymptotic Notation & Complexity Analysis

Day 81 — Big-O, \(\Omega\), \(\Theta\), \(o\), and \(\omega\) formally

Stage VIII · concept day
Goal: State formal asymptotic definitions; prove bounds with explicit witnesses \(C,n_0\); use limit tests; prove sum/product properties; avoid common notation abuses.

Why this matters

“\(O(n^2)\)” is not a vague English vibe — it is a quantified statement about eventual domination. Interview folklore and blogs often abuse the notation. Today you prove bounds the way a discrete math course expects, preparing Days 82–84.

Note

No labs. Code appears only as static fragments to describe cost, never as a programming exercise.

Theory

Setting

We compare functions \(f,g:\mathbb{N}\to\mathbb{R}\) (or eventually nonnegative real functions on \(\mathbb{N}\)). In algorithms, \(f(n)\) is often a runtime or operation count for input size \(n\). Asymptotics care about large \(n\), not \(n=1\) special cases.

Big-O (upper bound)

Definition (Big-O). We write \(f(n)=O(g(n))\) as \(n\to\infty\) if there exist constants \(C>0\) and \(n_0\in\mathbb{N}\) such that for all \(n\ge n_0\), \[ |f(n)| \le C\,|g(n)|. \] When \(f,g\ge 0\) eventually, this is \(f(n)\le C g(n)\) for \(n\ge n_0\).

Words. \(f\) grows at most as fast as \(g\), up to a constant factor, for large \(n\).

Set notation. \(O(g)=\{f:\exists C,n_0\ \forall n\ge n_0,\ |f|\le C|g|\}\). Writing \(f=O(g)\) means \(f\in O(g)\). The “\(=\)” is not symmetric: \(n=O(n^2)\) but \(n^2\neq O(n)\).

Quantifiers carefully: \(\exists C>0\ \exists n_0\ \forall n\ge n_0:\ |f(n)|\le C|g(n)|\).

Big-Omega (lower bound)

Definition (\(\Omega\)). \(f(n)=\Omega(g(n))\) if there exist \(c>0\) and \(n_0\) such that for all \(n\ge n_0\), \[ |f(n)| \ge c\,|g(n)|. \] Words. \(f\) grows at least as fast as \(g\) (up to a positive constant).

Duality. For positive functions, \(f=O(g)\) iff \(g=\Omega(f)\).

Big-Theta (tight bound)

Definition (\(\Theta\)). \(f(n)=\Theta(g(n))\) if \(f=O(g)\) and \(f=\Omega(g)\). Equivalently, \(\exists c_1,c_2>0\) and \(n_0\) such that for \(n\ge n_0\), \[ c_1 |g(n)| \le |f(n)| \le c_2 |g(n)|. \] Words. \(f\) and \(g\) have the same asymptotic growth rate up to constants.

Little-o and little-omega

Definition. \(f(n)=o(g(n))\) if for every \(\varepsilon>0\) there exists \(n_0\) such that for \(n\ge n_0\), \(|f(n)|\le \varepsilon |g(n)|\). Equivalently \(\lim_{n\to\infty} f(n)/g(n)=0\) when the limit exists.
\(f=\omega(g)\) means \(g=o(f)\).

Relation. \(f=o(g)\) implies \(f=O(g)\) but not conversely (\(n=O(n)\) but not \(o(n)\)). Little-o is a strictly slower growth statement.

Limit tests (practical)

When \(g(n)\neq 0\) and the limit exists in \([0,\infty]\):

Limit \(L=\lim f/g\) Conclusion (nonnegative case)
\(0\le L<\infty\) \(f=O(g)\)
\(0<L\le\infty\) \(f=\Omega(g)\)
\(0<L<\infty\) \(f=\Theta(g)\)
\(L=0\) \(f=o(g)\)
\(L=\infty\) \(f=\omega(g)\)

If the limit does not exist, witnesses or \(\limsup/\liminf\) arguments may still work.

Algebra of Big-O (nonnegative functions)

If \(f_1=O(g_1)\) and \(f_2=O(g_2)\), then:

  1. Sum: \(f_1+f_2=O(g_1+g_2)\) and also \(O(\max(g_1,g_2))\) when \(g_i>0\) (since \(g_1+g_2\le 2\max\)).
  2. Product: \(f_1 f_2=O(g_1 g_2)\).
  3. Transitivity: if \(f=O(g)\) and \(g=O(h)\) then \(f=O(h)\).
  4. Constants: for \(k>0\), \(k\cdot f=\Theta(f)\).
  5. Max: \(\max(f,g)=\Theta(f+g)\) for nonnegative \(f,g\).

Sum rule of thumb. If \(f=\Theta(n^2)\) and \(g=\Theta(n)\), then \(f+g=\Theta(n^2)\) — the faster-growing term dominates.

Proving \(f\neq O(g)\)

Negation. \(f\neq O(g)\) means: for every \(C>0\) and every \(n_0\), there exists \(n\ge n_0\) with \(|f(n)|>C|g(n)|\).
Strategy: for arbitrary \(C,n_0\), produce a large \(n\) violating the inequality.

Algorithm language

Saying “the algorithm is \(O(n^2)\)” usually means: there is a cost function \(T(n)\) with \(T(n)=O(n^2)\) in the worst case (or average case if specified). A \(\Theta\) claim is stronger and preferred when true. An \(O\) claim is not falsified by a faster true rate: if \(T(n)=\Theta(n)\), it is still correct that \(T(n)=O(n^2)\), but loose.

Common abuses

  1. Writing \(O(2n)\) as if better than \(O(n)\) — same class: \(O(2n)=O(n)\).
  2. \(T(n)=O(1)+O(n)\) without simplifying to \(O(n)\).
  3. Mixing average and worst case in one symbol without labels.
  4. Claiming \(f=O(g)\) from a plot at \(n\le 20\) only.
  5. Writing \(T(n)=O(f(n))+O(g(n))\) instead of \(O(f+g)\) then not simplifying.
  6. Treating \(O\) as \(\Theta\) in conversation (“is \(O(n\log n)\)” meaning tight).

Common algorithm bound catalogue (reminders)

Fragment / algorithm idea Typical tight class
Single loop \(1..n\) \(\Theta(n)\)
Double independent loops \(\Theta(n^2)\)
Binary search \(\Theta(\log n)\)
Comparison sort (optimal worst-case class) \(\Theta(n\log n)\)
Subset enumeration \(\Theta(2^n\cdot\mathrm{poly})\)

These are reminders, not substitutes for proofs on a concrete \(T(n)\).

Worked examples

Example 1 — Prove \(3n+5=O(n)\).
For \(n\ge 1\), \(3n+5\le 3n+5n=8n\). Take \(C=8\), \(n_0=1\).

Example 2 — Prove \(n=\Theta(n)\).
\(c_1=c_2=1\), \(n_0=1\): \(n\le n\le n\).

Example 3 — Prove \(n^2\neq O(n)\).
For any \(C,n_0\), pick \(n>\max(n_0,C)\); then \(n^2>C n\).

Example 4 — \(5n^2+3n+1=\Theta(n^2)\).
Upper: \(n\ge 1\) ⇒ \(5n^2+3n+1\le 5n^2+3n^2+n^2=9n^2\).
Lower: \(\ge 5n^2\). Take \(c_1=5\), \(c_2=9\), \(n_0=1\).

Example 5 — \(\log n=O(n)\).
\(\lim (\log n)/n=0\), so \(\log n=o(n)\) hence \(O(n)\). Explicitly \(\log_2 n\le n\) for \(n\ge 1\) after adjusting constant: \(\log_2 n=(\ln n)/\ln 2\le n/\ln 2\) for \(n\ge 1\) (actually \(\ln n\le n-1\)).

Example 6 — Limit test.
\(f(n)=n(n+1)/2\), \(g(n)=n^2\). \(f/g=\frac12+\frac{1}{2n}\to\frac12\), so \(f=\Theta(n^2)\).

Example 7 — Sum of costs.
Loop A \(\Theta(n)\), loop B \(\Theta(n^2)\), sequential: \(\Theta(n)+\Theta(n^2)=\Theta(n^2)\).

Example 8 — Little-o.
\(n=o(n^2)\) because \(n/n^2=1/n\to 0\). But \(n\neq o(n)\).

Example 9 — Product.
If \(f=O(n)\), \(g=O(n)\), then \(fg=O(n^2)\). Witnesses multiply: \(f\le C_1 n\), \(g\le C_2 n\) ⇒ \(fg\le C_1 C_2 n^2\).

Example 10 — Negation practice.
\(2^n\neq O(n^{100})\): \(2^n/n^{100}\to\infty\) (standard calculus / L’Hôpital \(100\) times, or known exponential vs poly).

Exercises

A. Definitions

  1. Write \(O\), \(\Omega\), \(\Theta\) with quantifiers from memory.
  2. Write \(o\) with quantifiers; contrast with \(O\).
  3. Explain why \(f=O(g)\) is not symmetric equality.
  4. Negate \(f=O(g)\) carefully with quantifiers.
  5. Show for positive \(f,g\): \(f=O(g)\Leftrightarrow g=\Omega(f)\).
  6. True or false: if \(f=O(g)\) and \(g=O(f)\) then \(f=\Theta(g)\). Prove.

B. Prove or disprove

  1. Prove \(7n+100=O(n)\) with explicit \(C,n_0\).
  2. Prove \(n=O(n^2)\) and \(n^2=\Omega(n)\).
  3. Prove \(n^2\neq O(n\log n)\) for \(\log\) base \(2\).
  4. Prove \(2^{n+1}=\Theta(2^n)\).
  5. Prove \(2^{2n}\neq O(2^n)\).
  6. Prove \(\frac{n(n-1)}{2}=\Theta(n^2)\).
  7. Prove \(\max(f,g)=\Theta(f+g)\) for nonnegative \(f,g\).
  8. Prove or discuss: \(O(f+g)=O(\max(f,g))\) as sets (nonnegative).
  9. Show \(n=o(n^2)\) but \(n\neq o(n)\).
  10. Analyze \(f(n)=n\) and \(g(n)=n+(-1)^n n/2\): is \(f=\Theta(g)\)?

C. Algorithmic interpretation

  1. Double loop for i=1..n: for j=1..n: O(1) — argue \(\Theta(n^2)\) body executions.
  2. If an algorithm is \(O(n^2)\) and \(\Omega(n^2)\) worst-case, what \(\Theta\) claim follows?
  3. Explain \(O(n^2)\) worst-case and \(O(n)\) best-case with two functions \(T_{\mathrm{worst}},T_{\mathrm{best}}\).
  4. Why drop constant factors and lower-order terms for large \(n\)?
  5. Give two examples where a looser \(O\) bound hides a practically important gap.

D. Properties and stretch

  1. Prove: if \(f_1=O(g_1)\), \(f_2=O(g_2)\) then \(f_1+f_2=O(\max(g_1,g_2))\) (nonnegative \(g_i\)).
  2. Prove: if \(f(n)\sim g(n)\) (ratio \(\to 1\)) then \(f=\Theta(g)\).
  3. Show there exist \(f,g>0\) with \(f\neq O(g)\) and \(g\neq O(f)\) (oscillatory).
  4. Prove \(n^k=o(2^n)\) for any fixed \(k\).
  5. Formalize polynomial time: \(T(n)=O(n^k)\) for some constant \(k\).

Deep dive — quantifier order drills

Correct \(O\): \(\exists C>0\ \exists n_0\ \forall n\ge n_0:\ |f|\le C|g|\).

Wrong variants students write:

  • \(\forall C\exists n_0\) — too strong (that is closer to little-o if \(C\) is arbitrary small).
  • \(\exists n_0\forall C\) — nonsense for \(O\).

Little-o: \(\forall\varepsilon>0\ \exists n_0\ \forall n\ge n_0:\ |f|\le\varepsilon|g|\).
The universal quantifier on \(\varepsilon\) is the difference that makes \(n=o(n)\) false.

Deep dive — proving sum/product rules

Sum. \(f_i\le C_i g_i\) for \(n\ge n_i\). Take \(n_0=\max n_i\), \(C=\max(C_1,C_2)\): \[ f_1+f_2\le C_1 g_1+C_2 g_2\le C(g_1+g_2)\le 2C\max(g_1,g_2). \]

Product. \(f_1 f_2\le C_1 C_2 g_1 g_2\) for \(n\ge\max n_i\) (nonnegative case).

Additional worked examples

Example 11 — \(n\log n=O(n^{1.5})\).
\((\log n)/n^{0.5}\to 0\), so eventually \(\log n\le n^{0.5}\), hence \(n\log n\le n^{1.5}\).

Example 12 — \(\Theta\) sandwich for \(n^3+100n\).
Lower: \(\ge n^3\). Upper: \(\le n^3+100n^3=101n^3\) for \(n\ge 1\).

Example 13 — Not \(\Theta\).
\(f(n)=n\) if \(n\) even, \(n^2\) if \(n\) odd: \(f\neq O(n)\) and careful analysis vs \(n^2\).

Example 14 — Algorithm false friend.
“Two nested loops” is not automatically \(n^2\) if bounds are \(i=1..n\), \(j=1..i\) still \(\Theta(n^2)\), but \(j=1..\log n\) is \(\Theta(n\log n)\).

Example 15 — Limit fails to exist.
\(f(n)=n(2+\sin n)\), \(g(n)=n\): ratio oscillates in \([1,3]\), still \(\Theta(n)\).

More exercises

  1. Prove \(100n+7=O(n)\) with \(C=101\), find minimal integer \(n_0\) for that \(C\).
  2. Prove \(\log(n!)=O(n\log n)\) without Stirling (bound \(\log(n!)\le n\log n\)).
  3. Prove \(\log(n!)=\Omega(n\log n)\) by \(\log(n!)\ge (n/2)\log(n/2)\).
  4. Show \(O(n)+O(n^2)=O(n^2)\) as sets of functions (nonnegative).
  5. Negate \(f=\Omega(g)\) carefully.
  6. CS: explain why “is \(O(n^2)\)” in an interview should often be upgraded to \(\Theta\) discussion.

Selected mini-solutions

  1. \(7n+100\le 7n+100n=107n\) for \(n\ge 1\).
  2. \(2^{n+1}=2\cdot 2^n\).
  3. \(2^{2n}/2^n=2^n\to\infty\).
  4. Repeated L’Hôpital or ratio \((n+1)^k/2^{n+1}\div(n^k/2^n)\to 1/2\).

Common pitfalls

Pitfall Fix
Treating \(O\) as \(\Theta\) \(O\) is only upper bound
Hiding \(n_0\) dependence on \(C\) Order is \(\exists C\exists n_0\)
Proving for one \(n\) only Need all \(n\ge n_0\)
Using \(\log\) without base Bases differ by constants: \(\Theta\) same
Saying “\(O(2n)\) better than \(O(n)\)” Same class
Confusing \(o\) quantifiers with \(O\) \(\forall\varepsilon\) vs \(\exists C\)

Study notes — asymptotic cheat card

Want Means
\(f=O(g)\) \(\exists C,n_0:\ n\ge n_0\Rightarrow |f|\le C|g|\)
\(f=\Omega(g)\) \(\exists c,n_0:\ |f|\ge c|g|\)
\(f=\Theta(g)\) both \(O\) and \(\Omega\)
\(f=o(g)\) \(\forall\varepsilon\exists n_0:\ |f|\le\varepsilon|g|\)
Limit \(L\in(0,\infty)\) \(\Theta\)
Limit \(0\) \(o\) (hence \(O\))
Limit \(\infty\) \(\omega\) (hence \(\Omega\))

Synthesis — asymptotics workout

S1. Write \(O,\Omega,\Theta,o\) with full quantifiers from memory.

S2. Prove \(4n^2+3n+2=\Theta(n^2)\) with explicit \(c_1,c_2,n_0\).

S3. Prove \(n\log n\neq O(n)\) and \(n\log n=O(n^{1.5})\).

S4. Prove \(2^{n}\neq O(n^{100})\) via limits or ratios.

S5. Negate \(f=O(g)\); use it to show \(n^2\neq O(n)\).

S6. Prove sum rule: \(f=O(n)\), \(g=O(n^2)\) ⇒ \(f+g=O(n^2)\).

S7. Explain \(T=O(n^2)\) vs \(T=\Theta(n^2)\) for a nested loop.

S8. Limit test: classify \(f(n)=n(n+1)(n+2)/6\) vs \(g(n)=n^3\).

Checkpoint

  • Can write \(O/\Omega/\Theta/o\) with quantifiers
  • Can prove simple polynomial bounds with explicit \(C,n_0\)
  • Can prove \(n^2\neq O(n)\) style negations
  • Can use limit tests
  • Can apply sum/product rules
  • Exercises A–C done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — limit test with proof obligations

Proposition. Suppose \(f,g>0\) and \(L=\lim_{n\to\infty}f(n)/g(n)\) exists in \([0,\infty]\).

  1. If \(L<\infty\) then \(f=O(g)\).
  2. If \(L>0\) then \(f=\Omega(g)\).
  3. If \(0<L<\infty\) then \(f=\Theta(g)\).
  4. If \(L=0\) then \(f=o(g)\).
  5. If \(L=\infty\) then \(f=\omega(g)\).

Proof of (1). If \(L<\infty\), the sequence \(f/g\) is eventually bounded, say \(f/g\le C\) for \(n\ge n_0\) (e.g. \(C=L+1\) if \(L\) finite). Thus \(f\le C g\).
Proof of (4). \(L=0\) means \(\forall\varepsilon>0\) eventually \(f/g<\varepsilon\), which is exactly \(f=o(g)\).

When the limit fails. Use \(\limsup\) for \(O\) and \(\liminf\) for \(\Omega\), or construct explicit witnesses. Example: \(f(n)=n(2+\sin n)\) still \(\Theta(n)\) even though \(f/n\) has no single limit if one worries about \(\sin n\) density — actually \(\sin n\) is dense in \([-1,1]\) but bounded, so \(1\le 2+\sin n\le 3\) gives sandwich.

Deeper theory — polynomial \(\Theta\) class

Theorem. If \(p(n)=a_d n^d+\cdots+a_0\) with \(a_d\neq 0\) and real coefficients, then \(p(n)=\Theta(n^d)\) as \(n\to\infty\) through positives large enough that \(p\) keeps the sign of \(a_d\) (for algorithms, usually \(a_d>0\) and \(p>0\)).

Proof sketch. Factor \(p(n)=n^d\bigl(a_d+a_{d-1}/n+\cdots+a_0/n^d\bigr)\). The expression in parentheses tends to \(a_d\neq 0\), so it is bounded between \(|a_d|/2\) and \(2|a_d|\) for large \(n\). Multiply by \(n^d\).

Worked examples — witness hunting

Example 16 — \(n^2+100n=\Theta(n^2)\) with explicit constants.
Upper: for \(n\ge 1\), \(n^2+100n\le n^2+100n^2=101n^2\).
Lower: \(n^2+100n\ge n^2\). So \(c_1=1\), \(c_2=101\), \(n_0=1\).

Example 17 — Prove \(\log_2(n!)=O(n\log_2 n)\).
\(n!\le n^n\) ⇒ \(\log_2(n!)\le n\log_2 n\). \(C=1\), \(n_0=2\).

Example 18 — Prove \(\log_2(n!)=\Omega(n\log_2 n)\).
For \(n\ge 2\), \(n!\ge (n/2)^{n/2}\) (product of the largest \(n/2\) factors each \(\ge n/2\)). Thus \(\log_2(n!)\ge (n/2)\log_2(n/2)=\Omega(n\log n)\).

Example 19 — Nested loop count.
for i = 1..n: for j = 1..i: O(1) executes \(\sum_{i=1}^n i=n(n+1)/2=\Theta(n^2)\) times — not \(\Theta(n)\) just because the inner bound depends on \(i\).

Extra exercises — asymptotic proofs

  1. Prove \(5n^3+2n=\Theta(n^3)\) with \(c_1,c_2,n_0\).
  2. Prove \(n^{1.1}\neq O(n\log n)\).
  3. Prove \(3^{n}=O(4^n)\) and \(4^n\neq O(3^n)\).
  4. Show \(O(n)\cdot O(n)=O(n^2)\) as a product of classes (nonnegative functions).
  5. Negate \(f=\Theta(g)\) carefully (two-sided failure modes).
  6. For \(T(n)=2T(n/2)+n\) with \(T(1)=1\) on powers of two, prove by induction \(T(n)=n\log_2 n+n\) (exact), hence \(\Theta(n\log n)\).
  7. Explain why \(O(1)\) memory and \(O(n)\) time are independent claims.
  8. CS interview hygiene: rewrite “our API is \(O(n^2)\)” as a precise statement about a cost model.

Mini-solutions (selected)

  1. \(n^{1.1}/(n\log n)=n^{0.1}/\log n\to\infty\).
  2. \((3/4)^n\to 0\) so \(3^n=o(4^n)\); reverse ratio \(\to\infty\).
  3. Inductive step: \(T(2m)=2T(m)+2m=2(m\log_2 m+m)+2m=2m\log_2 m+4m=(2m)\log_2(2m)+2m\).

Closing synthesis card

Symbol Quantifiers Limit form
\(O\) \(\exists C\exists n_0\) \(L<\infty\)
\(\Omega\) \(\exists c\exists n_0\) \(L>0\)
\(\Theta\) both \(0<L<\infty\)
\(o\) \(\forall\varepsilon\exists n_0\) \(L=0\)

Always produce witnesses on exams unless a clean limit is given.

Tomorrow

Day 82 — Growth classes: ranking \(\Theta\) families.

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.

Day 83 — Loops to sums to bounds; amortized idea

Stage VIII · concept day
Goal: Translate nested loops to sums; bound sums by closed forms or integral ideas; set up best/worst/average; introduce amortized analysis idea (aggregate method, dynamic array doubling).

Why this matters

Runtime analysis is usually “count elementary steps → sum → asymptotics.” Master theorem (Day 84) handles recurrences; today handles straight-line nested iteration and the first amortized stories you meet for resizable arrays.

Note

No labs. Static pseudocode only; analyze on paper.

Theory

From loops to sums

Model. Each “elementary operation” costs \(1\). Loops contribute a sum over the iteration domain.

Single loop.

for i = 1..n:
    work O(1)

Cost \(T(n)=\sum_{i=1}^n \Theta(1)=\Theta(n)\).

Independent nested loops.

for i = 1..n:
  for j = 1..n:
      work O(1)

\(T(n)=\sum_{i=1}^n\sum_{j=1}^n 1=n^2=\Theta(n^2)\).

Triangular nested loops.

for i = 1..n:
  for j = 1..i:
      work O(1)

\(T(n)=\sum_{i=1}^n i = n(n+1)/2=\Theta(n^2)\).

Dependent bounds.

for i = 1..n:
  for j = i..n:
      work O(1)

\(\sum_{i=1}^n (n-i+1)=\sum_{k=1}^n k=\Theta(n^2)\).

Standard sum catalogue

Sum Closed form / bound
\(\sum_{i=1}^n 1\) \(n\)
\(\sum_{i=1}^n i\) \(n(n+1)/2=\Theta(n^2)\)
\(\sum_{i=1}^n i^2\) \(n(n+1)(2n+1)/6=\Theta(n^3)\)
\(\sum_{i=1}^n i^k\) (\(k\) fixed) \(\Theta(n^{k+1})\)
\(\sum_{i=1}^n \log i\) \(\Theta(n\log n)\) (Stirling / integral)
\(\sum_{i=0}^h 2^i\) \(2^{h+1}-1=\Theta(2^h)\)
\(\sum_{i=1}^n 1/i\) \(H_n=\Theta(\log n)\)

Bounding sums by integrals (idea)

For nondecreasing \(f\), \[ \int_0^n f(x)\,dx \le \sum_{i=1}^n f(i) \le f(n)+\int_0^{n-1} f(x)\,dx \] (pictorial staircase bounds). For nonincreasing, inequalities reverse appropriately.

Example. \(\int_1^n (1/x)\,dx=\ln n\) sandwiches \(H_n\): \(\ln(n+1)\le H_n\le 1+\ln n\), so \(H_n=\Theta(\log n)\).

Best / worst / average case (setup)

For input size \(n\), cost may depend on the particular input \(x\) with \(|x|=n\).

  • Worst case: \(T_{\mathrm{wc}}(n)=\max_{|x|=n} T(x)\).
  • Best case: \(T_{\mathrm{bc}}(n)=\min_{|x|=n} T(x)\).
  • Average case: \(T_{\mathrm{avg}}(n)=\sum_{|x|=n} T(x)P(x)\) under a stated distribution on inputs.

Always label which case. Average case requires a probability model (Day 85+).

Example. Linear search for a key in an array of \(n\) distinct keys: best \(\Theta(1)\), worst \(\Theta(n)\), average \(\Theta(n)\) under uniform position of the key (including failure variants carefully).

Amortized analysis (idea)

Problem. Some operations are occasionally expensive (array resize) but rare. Amortized cost of an operation in a sequence is a bound on average cost over the sequence, not a probability.

Aggregate method. If any sequence of \(n\) operations costs at most \(T(n)\) total, the amortized cost per operation is \(T(n)/n\).

Dynamic array doubling.

  • Array capacity \(c\), size \(m\).
  • Append: if \(m<c\), cost \(1\); if \(m=c\), allocate \(2c\), copy \(m\) elements, then insert — cost \(\Theta(m)\), then \(c\leftarrow 2c\).
  • From empty to \(n\) appends: resizes at sizes \(1,2,4,\ldots,2^{k}\) with \(2^k<n\le 2^{k+1}\). Copy costs \(1+2+4+\cdots+2^k < 2n\).
  • Total cost of \(n\) appends: \(O(n)\) (all cheap inserts) \(+O(n)\) (all copies) \(=O(n)\).
  • Amortized \(O(1)\) per append.

Accounting / potential methods (awareness). Assign banked credits or a potential function \(\Phi\) so amortized cost \(=\text{actual}+\Delta\Phi\) is bounded; aggregate doubling is enough for this volume.

Not the same as average case. Amortized is adversarial sequences with total bound; average case is random inputs.

Nested loops with geometric iteration

for i = 1,2,4,...,2^k < n:
    work O(i)   # or O(n), depending

Number of iterations \(O(\log n)\). If work per iteration is \(O(n)\), total \(O(n\log n)\). If work is \(O(i)\), total \(O(n)\).

Sequential vs nested

Sequential blocks: add costs. Nested: multiply iteration counts (when inner independent of outer cost structure) — more precisely, sum the inner costs.

Worked examples

Example 1 — Triangular.
\(\sum_{i=1}^n\sum_{j=1}^i 1=\sum_i i=\Theta(n^2)\).

Example 2 — Three nested.
Triple independent loops \(n\times n\times n\): \(\Theta(n^3)\).

Example 3 — Log factor.

for i=1..n:
  j=n
  while j>=1:
    j = j//2

Inner runs \(\Theta(\log n)\) times; total \(\Theta(n\log n)\).

Example 4 — Harmonic.

for i=1..n:
  for j=1..n step i:  # j = i,2i,3i,...
      O(1)

Inner runs \(\lfloor n/i\rfloor\) times; total \(\sum_{i=1}^n n/i = n H_n=\Theta(n\log n)\).

Example 5 — Best/worst.
Insertion into sorted array at beginning vs end may differ if shifting costs; specify model.

Example 6 — Doubling aggregate.
\(n=10\) appends: copies at capacities \(1,2,4,8\) costing \(1+2+4+8=15\) plus \(10\) writes = \(25=O(n)\).

Example 7 — Sum of squares.
\(\sum_{i=1}^n i^2=\Theta(n^3)\) so nested

for i=1..n:
  for j=1..i:
    for k=1..i:
        O(1)

is \(\sum_i i^2=\Theta(n^3)\).

Example 8 — Geometric series.
Cost \(1+2+4+\cdots+2^{h}=\Theta(2^h)\). If \(2^h=\Theta(n)\), total \(\Theta(n)\).

Example 9 — Average linear search.
Successful search, key uniform in \(n\) positions: expected comparisons \((n+1)/2=\Theta(n)\).

Example 10 — Misleading “each op \(O(n)\)”.
\(n\) appends each “\(O(n)\) worst” would suggest \(O(n^2)\), but amortized \(O(1)\) gives \(O(n)\) total — the point of amortization.

Exercises

A. Loop translations

  1. Cost of double loop \(i=1..n\), \(j=1..n\).
  2. Cost of \(i=1..n\), \(j=1..i\).
  3. Cost of \(i=1..n\), \(j=i..n\).
  4. Cost of \(i=1..n\), \(j=1..n\), \(k=1..n\).
  5. Cost of \(i=1..n\), inner while \(j\leftarrow n, n/2, n/4,\ldots\)
  6. Analyze Example 4 style: for \(i=1..n\) for \(j=i; j\le n; j+=i\).

B. Sums and bounds

  1. Prove \(\sum_{i=1}^n i=\Theta(n^2)\) with sandwich \(n^2/2\le\sum i\le n^2\).
  2. Show \(H_n=\Theta(\log n)\) using integral idea.
  3. Bound \(\sum_{i=1}^n i^3\) as \(\Theta(n^4)\) (formula or integral).
  4. Show \(\sum_{i=1}^n \log i=\Theta(n\log n)\).
  5. Evaluate \(\sum_{k=0}^{h} 3^k\) exactly and as \(\Theta\).

C. Cases

  1. Define worst/best/average for finding the maximum in an unsorted array of \(n\) elements (comparisons).
  2. Binary search comparisons: worst-case \(\Theta(\log n)\); best-case \(\Theta(1)\) if middle hits. Average under uniform is \(\Theta(\log n)\). Explain.
  3. Why is average case meaningless without a distribution?

D. Amortized

  1. Dynamic array doubling: show total copy cost over \(n\) appends is \(<2n\).
  2. What if we resize by \(+1\) each time capacity is full? Total cost of \(n\) appends?
  3. What if we resize by \(\times 3\) instead of \(\times 2\)? Still amortized \(O(1)\)?
  4. Explain in prose: amortized \(\neq\) average-case probability.
  5. Aggregate method: if \(n\) ops cost \(\le 5n+100\), amortized cost?

E. Stretch

  1. Analyze:
for i=1..n:
  for j=1..i:
    for k=1..j:
        O(1)
  1. Loop \(i=1..n\) with \(O(i^2)\) work: total?
  2. Show \(\sum_{i=1}^n \lfloor n/i\rfloor =\Theta(n\log n)\).
  3. Potential idea (optional): \(\Phi=\text{size}\), show amortized append \(O(1)\) for doubling with a potential argument outline.
  4. CS literacy: name two structures beyond arrays that use amortized \(O(1)\) stories (e.g. union-find ackermann, splay trees — names only).

Deep dive — sum bounds toolkit

Goal Technique
Exact Closed form (\(\sum i\), geometric)
\(\Theta\) only Sandwich \(c_1 n^{k+1}\le\sum i^k\le c_2 n^{k+1}\)
Harmonic Integral of \(1/x\)
Decreasing \(f\) \(\int_1^{n+1} f\le\sum_{1}^n f\le f(1)+\int_1^n f\)

Example proof that \(\sum_{i=1}^n i=\Theta(n^2)\) without formula:
\(\sum_{i=\lceil n/2\rceil}^n i\ge (n/2)\cdot(n/2)=n^2/4\), and \(\sum_{i=1}^n i\le n\cdot n=n^2\).

Deep dive — amortized vs average vs worst

Concept Adversary? Randomness? Bound type
Worst-case single op Yes No per operation
Average-case Distribution on inputs Yes expectation
Amortized Worst sequence No average over sequence of ops

Dynamic array: a single append can be \(\Theta(n)\) worst-case, but amortized \(O(1)\), and there is no probability required.

Additional worked examples

Example 11 — Harmonic nested.
\(\sum_{i=1}^n\lfloor n/i\rfloor\): for each \(i\), about \(n/i\) multiples; total \(\Theta(n\log n)\).

Example 12 — Geometric outer.
\(i=1,2,4,\ldots,2^k\le n\), work \(O(n)\) each: \(O(n\log n)\) iterations count.

Example 13 — Resize +1 disaster.
Appending \(n\) times with capacity growth \(+1\): copy costs \(1+2+\cdots+n=\Theta(n^2)\).

Example 14 — Average search.
Unsuccessful search in unordered list always \(\Theta(n)\); successful uniform: \((n+1)/2\).

Example 15 — Triple dependent.
\(\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j 1=\sum_i\sum_j j=\sum_i j(j+1)/2=\Theta(n^3)\).

More exercises

  1. Bound \(\sum_{i=1}^n\sqrt{i}\) as \(\Theta(n^{3/2})\) via integrals.
  2. Analyze:
s=0
for i=1..n:
  for j=1..n:
    if j % i == 0: s++
  1. Amortized: \(n\) ops, total cost \(n\log n\) — amortized cost?
  2. Best/worst for finding if array is sorted (comparisons).
  3. Show doubling from capacity \(1\) to \(\ge n\) copies \(<2n\) elements total.
  4. Loop \(i=n; i\ge 1; i=i//3\) with \(O(1)\) body: \(\Theta(\log n)\).
  5. Explain why average-case quicksort \(\Theta(n\log n)\) is not an amortized claim.
  6. CS literacy: name one structure with expensive occasional rebuild amortized away.

Selected mini-solutions

  1. \(n^2\).
  2. \(n(n+1)/2=\Theta(n^2)\).
  3. \(\ln(n+1)\le H_n\le 1+\ln n\).
  4. Copies \(1+2+4+\cdots+2^{k}<2^{k+1}\le 2n\).
  5. \(+1\) growth: \(\Theta(n^2)\) total.

Common pitfalls

Pitfall Fix
Multiplying loop bounds always Dependent bounds need careful sums
\(\sum_{i=1}^n i = O(n)\) No: \(\Theta(n^2)\)
Worst-case of each op × \(n\) May overcount; consider amortized
Average without model State distribution
Integral bounds as exact equality They sandwich
Calling amortized “expected” No probability required

Checkpoint

  • Can translate nested loops to sums
  • Know \(\sum i\), \(\sum i^2\), \(H_n\), geometric sums
  • Can set up best/worst/average
  • Can prove amortized \(O(1)\) append for doubling arrays
  • Exercises A–D done

Two personal takeaways:

  1. …
  2. …

Tomorrow

Day 84 — Master theorem and recursion trees.

Day 84 — Master theorem, recursion trees, Akra–Bazzi awareness

Stage VIII · concept day
Goal: State the Master theorem’s three cases formally; apply to mergesort, binary search, Strassen shape; use recursion trees; know when Master does not apply; one paragraph on Akra–Bazzi.

Why this matters

Divide-and-conquer recurrences are the standard model for mergesort, many FFT-style algorithms, and geometric divide-and-conquer. Master theorem turns a recurrence shape into a \(\Theta\) bound without unrolling every level by hand — when hypotheses hold.

Note

No labs. Recurrences and proofs on paper only.

Theory

Standard form

Consider recurrences on \(n\) (think powers of \(b\) for cleanliness, or assume \(T\) defined on reals / floors ignored for \(\Theta\)): \[ T(n) = a\, T\Bigl(\frac{n}{b}\Bigr) + f(n),\qquad a\ge 1,\ b>1, \] with \(T(n)=\Theta(1)\) for \(n\le n_0\).
Interpretation: \(a\) subproblems, each of size \(n/b\), plus \(f(n)\) divide/combine work.

Master theorem (three cases)

Compare \(f(n)\) to \(n^{\log_b a}\) (the critical power).

Case 1. If \(f(n)=O\bigl(n^{\log_b a-\varepsilon}\bigr)\) for some constant \(\varepsilon>0\), then \[ T(n)=\Theta\bigl(n^{\log_b a}\bigr). \] (Leaf work dominates.)

Case 2. If \(f(n)=\Theta\bigl(n^{\log_b a}\log^{k} n\bigr)\) for \(k\ge 0\) (common textbook: \(k=0\) so \(f=\Theta(n^{\log_b a})\)), then
- if \(k=0\): \(T(n)=\Theta\bigl(n^{\log_b a}\log n\bigr)\);
- more generally \(T(n)=\Theta\bigl(n^{\log_b a}\log^{k+1} n\bigr)\).

(Standard CLRS Case 2 is \(f=\Theta(n^{\log_b a})\) ⇒ \(T=\Theta(n^{\log_b a}\log n)\).)

Case 3. If \(f(n)=\Omega\bigl(n^{\log_b a+\varepsilon}\bigr)\) for some \(\varepsilon>0\) and the regularity condition \(a f(n/b)\le c f(n)\) for some \(c<1\) and large \(n\), then \[ T(n)=\Theta(f(n)). \] (Root work dominates.)

Critical exponent

\(\log_b a\) is the unique number satisfying \(a = b^{\log_b a}\). Number of leaves in a perfect recursion tree is \(a^{h}\) with \(n/b^{h}=1\) ⇒ \(h=\log_b n\), leaves \(a^{\log_b n}=n^{\log_b a}\).

Recursion tree / tree method

Unroll: \[ T(n)=f(n)+a f(n/b)+a^2 f(n/b^2)+\cdots+a^{h}T(\Theta(1)). \] Level \(i\) costs \(a^i f(n/b^i)\) (approximately). Sum over \(i=0..h-1\) plus \(\Theta(n^{\log_b a})\) leaf level. Cases of Master correspond to geometric series dominated by first term, balanced, or last term.

Classic examples

Algorithm Recurrence shape \(\log_b a\) \(f(n)\) Case \(T(n)\)
Binary search \(T=T(n/2)+\Theta(1)\) \(0\) \(\Theta(1)\) 2 \(\Theta(\log n)\)
Mergesort \(T=2T(n/2)+\Theta(n)\) \(1\) \(\Theta(n)\) 2 \(\Theta(n\log n)\)
Naive recursive mult (some forms) varies
Strassen matrix mult \(T=7T(n/2)+\Theta(n^2)\) \(\log_2 7\approx 2.81\) \(\Theta(n^2)\) 1 \(\Theta(n^{\log_2 7})\)
Binary tree walk all nodes not always Master form

When Master does not apply

  1. Subproblem sizes unequal: \(T(n)=T(\lfloor n/3\rfloor)+T(\lceil 2n/3\rceil)+n\).
  2. \(f\) too close to boundary without log factors handled (gap between cases) — need extended Master or tree sum.
  3. \(a\) or \(b\) not constants (e.g. \(a=n\)).
  4. Subtractive recurrences \(T(n)=T(n-1)+\Theta(n)\) — use summation, not Master.
  5. Floors/ceilings usually OK for \(\Theta\) but messy for exact identities.
  6. Regularity fails in pathological Case 3 candidates.

Akra–Bazzi (awareness, one paragraph)

Akra–Bazzi theorem generalizes Master to \[ T(x)=\sum_{i=1}^k a_i T(b_i x)+g(x) \] with \(a_i>0\), \(0<b_i<1\), under mild regularity on \(g\). One solves for \(p\) in \(\sum a_i b_i^{p}=1\), then \[ T(x)=\Theta\Bigl(x^p\Bigl(1+\int_1^x \frac{g(u)}{u^{p+1}}\,du\Bigr)\Bigr). \] Use: know it exists for uneven splits; apply Master when the standard form fits; do not compute Akra–Bazzi integrals on the gate unless specified.

Unrolling a non-Master recurrence

\(T(n)=T(n-1)+\Theta(n)\), \(T(1)=\Theta(1)\) ⇒ \(T(n)=\Theta\bigl(\sum_{k=1}^n k\bigr)=\Theta(n^2)\).
\(T(n)=2T(n-1)+\Theta(1)\) ⇒ \(T(n)=\Theta(2^n)\).

Worked examples

Example 1 — Mergesort.
\(a=2,b=2\), \(\log_b a=1\), \(f=n=\Theta(n^{\log_b a})\). Case 2: \(T=\Theta(n\log n)\).

Example 2 — Binary search.
\(a=1,b=2\), \(\log_b a=0\), \(f=\Theta(1)=\Theta(n^0)\). Case 2: \(T=\Theta(\log n)\).

Example 3 — Case 1.
\(T(n)=9T(n/3)+n\). \(\log_3 9=2\), \(f=n=O(n^{2-\varepsilon})\) with \(\varepsilon=1\). \(T=\Theta(n^2)\).

Example 4 — Case 3.
\(T(n)=3T(n/4)+n^5\). \(\log_4 3\approx 0.79\), \(f=n^5=\Omega(n^{0.79+\varepsilon})\). Regularity: \(3(n/4)^5=3n^5/1024\le c n^5\) for \(c=3/1024<1\). \(T=\Theta(n^5)\).

Example 5 — Strassen shape.
\(T=7T(n/2)+\Theta(n^2)\). \(\log_2 7>\ 2\), Case 1: \(T=\Theta(n^{\log_2 7})\).

Example 6 — Tree sum Case 2.
Levels each cost \(\Theta(n)\) for mergesort; \(\log_2 n\) levels → \(\Theta(n\log n)\).

Example 7 — Gap caution.
\(T=2T(n/2)+n/\log n\) may fall outside the three simple cases; needs extended analysis (awareness).

Example 8 — Not Master.
\(T(n)=T(n-1)+T(n-2)+\Theta(1)\) (Fibonacci-like) — characteristic equation / generating functions, not Master.

Example 9 — \(T(n)=4T(n/2)+n^2\log n\).
\(\log_2 4=2\), \(f=n^2\log n=\Theta(n^{\log_b a}\log n)\) extended Case 2: \(T=\Theta(n^2\log^2 n)\).

Example 10 — Verify by unrolling small.
\(T(n)=2T(n/2)+n\), \(T(1)=0\): \(T(2)=2\), \(T(4)=8\), \(T(8)=24\) pattern \(T(n)=n\log_2 n\).

Exercises

A. Identify cases

  1. \(T=2T(n/2)+n^3\).
  2. \(T=2T(n/2)+\sqrt{n}\).
  3. \(T=4T(n/2)+n\).
  4. \(T=4T(n/2)+n^2\).
  5. \(T=4T(n/2)+n^3\).
  6. \(T=T(n/2)+\Theta(1)\).
  7. \(T=9T(n/3)+n^2\).
  8. \(T=3T(n/2)+n\).

B. Algorithm shapes

  1. Write mergesort’s recurrence and solve.
  2. Write binary search’s recurrence and solve.
  3. Strassen: why is \(\log_2 7\) the exponent? Compare to naive \(\Theta(n^3)\).
  4. Karatsuba multiplication shape \(T=3T(n/2)+\Theta(n)\): solve.
  5. Closest pair divide-and-conquer often \(T=2T(n/2)+\Theta(n)\): \(T=?\)

C. Trees and non-Master

  1. Draw recursion tree levels for \(T=3T(n/4)+n\) and sum geometrically.
  2. Solve \(T(n)=T(n-1)+\Theta(n)\) by summation.
  3. Solve \(T(n)=2T(n-1)+\Theta(n)\) (homogeneous + particular or unroll).
  4. Explain why \(T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+\Theta(n)\) is still \(\Theta(n\log n)\) by intuition (equal split).
  5. Give three reasons Master might not apply to a recurrence you invent.

D. Regularity and edges

  1. Check regularity for \(T=2T(n/2)+n^2\).
  2. Check regularity for \(T=2T(n/2)+n/\log n\) — does Case 3 fire?
  3. State Akra–Bazzi in one paragraph in your own words.
  4. For \(T(n)=T(n/3)+T(2n/3)+\Theta(n)\), identify \(p\) idea (\(\ (1/3)^p+(2/3)^p=1\)) without computing the integral.

E. Stretch

  1. Prove Case 2 for \(f=\Theta(n^{\log_b a})\) by summing \(\sum_{i=0}^{h-1} a^i (n/b^i)^{\log_b a}\).
  2. Extended Case 2: if \(f=\Theta(n^{\log_b a}\log n)\), show tree levels give extra log.
  3. Compare Master Case 1 leaf dominance to “most work at bottom of recursion tree” intuition.

Deep dive — recursion tree sum (Case 2)

For mergesort-like \(T(n)=2T(n/2)+cn\):

Level \(i\) Subproblem size Cost at level
\(0\) \(n\) \(cn\)
\(1\) \(n/2\) \(2\cdot c(n/2)=cn\)
\(i\) \(n/2^i\) \(cn\)
\(h=\log_2 n\) \(1\) \(cn\) (leaves total \(\Theta(n)\) if \(T(1)=\Theta(1)\) careful)

About \(\log_2 n\) levels each \(cn\) ⇒ \(T(n)=\Theta(n\log n)\).

Case 1 geometric: level costs \(a^i f(n/b^i)\) decrease geometrically; sum dominated by leaves \(n^{\log_b a}\).
Case 3: dominated by root \(f(n)\).

Deep dive — Case 3 regularity examples

  • \(f(n)=n^2\), \(a=2\), \(b=2\): \(a f(n/b)=2(n/2)^2=n^2/2\le c n^2\) for \(c=1/2\). OK.
  • \(f(n)=n\), \(a=2\), \(b=2\): \(2\cdot(n/2)=n\not\le c n\) for \(c<1\). Regularity fails — and this is Case 2, not Case 3.
  • Pathological \(f\) can satisfy polynomial growth vs \(n^{\log_b a}\) but fail regularity — rare in algorithms courses.

Additional worked examples

Example 11 — \(T=8T(n/2)+n^2\).
\(\log_2 8=3\), \(f=n^2=O(n^{3-\varepsilon})\), Case 1: \(\Theta(n^3)\).

Example 12 — \(T=T(n/2)+n\).
\(\log_2 1=0\), \(f=n=\Omega(n^{0+\varepsilon})\), regularity \(1\cdot(n/2)\le c n\) for \(c=1/2\). Case 3: \(\Theta(n)\).

Example 13 — Unroll \(T(n)=T(n-1)+n\).
\(T(n)=\Theta(1)+\sum_{k=2}^n k=\Theta(n^2)\).

Example 14 — Karatsuba.
\(T(n)=3T(n/2)+\Theta(n)\), \(\log_2 3\approx 1.58\), Case 1: \(\Theta(n^{\log_2 3})\).

Example 15 — Gap.
\(f(n)=n/\log n\) with \(a=b=2\): between Case 1 and 2; needs extended tools — note “Master silent.”

More exercises

  1. Solve \(T=16T(n/4)+n^2\).
  2. Solve \(T=2T(n/4)+1\).
  3. Draw 4 levels of tree for \(T=3T(n/2)+n\) and estimate sum.
  4. Why floors/ceilings usually do not change \(\Theta\) answers for Master-shaped recurrences (prose).
  5. Give a recurrence for naive recursive Fibonacci and solve by other means.
  6. Strassen vs naive: for which \(n\) (qualitatively) might constants make naive faster?
  7. Write Akra–Bazzi applicability in 4 sentences for \(T(n)=T(\lfloor n/5\rfloor)+T(\lceil 4n/5\rceil)+\Theta(n)\).

Selected mini-solutions

  1. \(\log_2 2=1\), \(f=n^3\) Case 3: \(\Theta(n^3)\).
  2. \(\log_2 4=2\), \(f=n\) Case 1: \(\Theta(n^2)\).
  3. \(f=n^2=\Theta(n^{\log_b a})\) Case 2: \(\Theta(n^2\log n)\).
  4. \(T=\Theta(n^{\log_2 7})\).
  5. Summation not Master.

Common pitfalls

Pitfall Fix
Comparing \(f\) to \(a\) or \(b\) instead of \(n^{\log_b a}\) Critical exponent first
Forgetting Case 3 regularity Check \(a f(n/b)\le c f(n)\)
Applying Master to \(T(n-1)\) forms Summation instead
Claiming Strassen is \(O(n^2)\) Exponent is \(\log_2 7>2\)
Ignoring \(\log\) factors on the boundary Extended Case 2
Forcing a case when none applies Say so; use tree sum

Study notes — Master quick compare

For \(T=aT(n/b)+f(n)\), set \(c_{\mathrm{crit}}=\log_b a\):

Relation of \(f\) to \(n^{c_{\mathrm{crit}}}\) Case \(T\)
polynomially smaller 1 \(\Theta(n^{c_{\mathrm{crit}}})\)
equal (std) 2 \(\Theta(n^{c_{\mathrm{crit}}}\log n)\)
polynomially larger + regularity 3 \(\Theta(f)\)

Mergesort: Case 2 → \(n\log n\). Binary search: Case 2 → \(\log n\). Strassen: Case 1 → \(n^{\log_2 7}\).

Synthesis — Master theorem workout

S1. State all three cases with \(\varepsilon\) and regularity.

S2. Solve: \(T=2T(n/2)+n\); \(T=4T(n/2)+n\); \(T=4T(n/2)+n^3\); \(T=T(n/2)+1\).

S3. Strassen shape → \(\Theta\) class; compare to \(n^3\).

S4. Draw recursion tree for \(T=3T(n/3)+n\) and sum.

S5. Why \(T(n)=T(n-1)+\Theta(n)\) is not Master; solve it.

S6. Check regularity for \(T=2T(n/2)+n^2\).

S7. Akra–Bazzi purpose in 3–5 sentences.

S8. Invent a recurrence where Master does not apply; say why.

Checkpoint

  • Can state three Master cases with hypotheses
  • Can solve mergesort, binary search, Strassen shape
  • Can draw/sum a recursion tree for geometric levels
  • Know when Master fails
  • Can mention Akra–Bazzi purpose
  • Exercises A–C done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — Case 1 leaf dominance (tree sum)

Identity at the critical power. For every level \(i\), \[ a^i\Bigl(\frac{n}{b^i}\Bigr)^{\log_b a}=n^{\log_b a}. \] So if \(f(n)=n^{\log_b a}\), every level costs the same \(\Theta(n^{\log_b a})\) (Case 2 template).

Case 1. Suppose \(f(n)\le K n^{\log_b a-\varepsilon}\) for constants \(K,\varepsilon>0\) and large \(n\). Then \[ a^i f\!\left(\frac{n}{b^i}\right) \le K a^i \Bigl(\frac{n}{b^i}\Bigr)^{\log_b a-\varepsilon} = K n^{\log_b a-\varepsilon}\, b^{i\varepsilon} = K n^{\log_b a}\cdot n^{-\varepsilon}\cdot b^{i\varepsilon}. \] Along the tree, \(i\) runs from \(0\) to \(h-1\) with \(h=\log_b n\), so \(b^{h}=n\) and the factors \(n^{-\varepsilon}b^{i\varepsilon}=(b^{i}/n)^{\varepsilon}\le 1\). Summing the geometric series of level costs (each a fixed fraction smaller than the leaf scale when \(\varepsilon>0\)) yields \[ \sum_{i=0}^{h-1} a^i f(n/b^i)=O\bigl(n^{\log_b a}\bigr). \] Adding the leaf contribution \(\Theta(n^{\log_b a})\) gives \(T(n)=\Theta(n^{\log_b a})\).

Intuition. Case 1 = most work at the bottom of the tree; Case 3 = most work at the root; Case 2 = roughly equal work per level, times \(\Theta(\log n)\) levels.

Deeper theory — when not to force Master

Recurrence Why Master fails Tool
\(T(n)=T(n-1)+\Theta(n)\) not \(n/b\) form summation
\(T(n)=T(\lfloor n/3\rfloor)+T(\lceil 2n/3\rceil)+\Theta(n)\) uneven split Akra–Bazzi / tree
\(T(n)=nT(n/2)+\Theta(1)\) \(a\) not constant other
\(T(n)=2T(n/2)+n/\log n\) gap case extended Master / integrals
\(T(n)=T(n-1)+T(n-2)+\Theta(1)\) Fibonacci-like char. equation

Worked examples — case identification battery

Example 16 — \(T=2T(n/2)+n^2\).
\(\log_2 2=1\), \(f=n^2=\Omega(n^{1+\varepsilon})\), regularity \(2(n/2)^2=n^2/2\le c n^2\) with \(c=1/2\). Case 3: \(\Theta(n^2)\).

Example 17 — \(T=9T(n/3)+n\).
\(\log_3 9=2\), \(f=n=O(n^{2-\varepsilon})\), Case 1: \(\Theta(n^2)\).

Example 18 — \(T=T(n/2)+1\).
\(\log_2 1=0\), \(f=\Theta(1)=\Theta(n^0)\), Case 2: \(\Theta(\log n)\).

Example 19 — Karatsuba.
\(T=3T(n/2)+\Theta(n)\), \(\log_2 3\approx 1.585\), Case 1: \(\Theta(n^{\log_2 3})\).

Example 20 — Tree for \(T=3T(n/2)+n\).
\(\log_2 3>1\), Case 1: leaves dominate, \(T=\Theta(n^{\log_2 3})\). Level costs grow geometrically toward the leaves.

Extra exercises — Master fluency

  1. Solve \(T=8T(n/2)+n^3\).
  2. Solve \(T=2T(n/4)+\sqrt{n}\).
  3. Check regularity for \(T=3T(n/3)+n^2\).
  4. Unroll \(T(n)=T(n-1)+2n\) to a closed \(\Theta\) form.
  5. Mergesort vs insertion sort growth: \(\Theta(n\log n)\) vs \(\Theta(n^2)\) — rank them.
  6. Why does \(T=2T(n/2)+n\log n\) fall into extended Case 2? State the \(\Theta\) answer \(\Theta(n\log^2 n)\).
  7. Give a one-paragraph explanation of Akra–Bazzi purpose for uneven splits.
  8. Invent three recurrences: one each for Cases 1–3; solve them.

Mini-solutions (selected)

  1. \(\log_2 8=3\), \(f=n^3=\Theta(n^{\log_b a})\), Case 2: \(\Theta(n^3\log n)\).
  2. \(\log_4 2=1/2\), \(f=n^{1/2}=\Theta(n^{\log_b a})\), Case 2: \(\Theta(\sqrt{n}\log n)\).
  3. \(T(n)=\Theta(n^2)\).

Closing synthesis card

Case \(f\) vs \(n^{\log_b a}\) \(T\)
1 polynomially smaller \(\Theta(n^{\log_b a})\)
2 same order (std) \(\Theta(n^{\log_b a}\log n)\)
3 polynomially larger + regularity \(\Theta(f)\)

Always: compute \(\log_b a\) first; then classify; then check regularity only for Case 3.

Tomorrow

Day 85 — Discrete probability on finite spaces.