Day 84 — Master theorem

Updated

July 30, 2026

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.