Chapter 19 — Key Takeaways
Solving Recurrence Relations: Merge Sort, Fibonacci, and the Master Theorem. A one-page reference to
reread before an exam. For the full derivations, see index.md.
The object: divide-and-conquer recurrences
$$T(n) = a\,T(n/b) + f(n), \qquad T(\text{small}) = \Theta(1)$$
| Symbol | Meaning | How to read it off the code |
|---|---|---|
| $a$ | number of recursive calls (branching factor) | count the return ...recurse(...) calls actually made |
| $b$ | shrink factor; each subproblem has size $n/b$ | the input passed to each call is $n/b$ |
| $f(n)$ | non-recursive (divide + combine) work | everything the body does except the recursive calls |
| $E = \log_b a$ | critical exponent; $n^E$ = total leaf work | compute once, then compare to $f(n)$ |
Floors/ceilings ($\lceil n/b \rceil$) do not change the $\Theta$ answer — analyze the clean version.
Method 1 — Recursion tree (always works)
| Level $i$ | Value |
|---|---|
| nodes | $a^i$ |
| size per node | $n/b^i$ |
| work at this level | $a^i\,f(n/b^i)$ |
| height of tree | $\log_b n$ |
| leaves / leaf work | $a^{\log_b n} = n^{\log_b a} = n^E$ |
$$T(n) = \sum_{i=0}^{\log_b n} a^i\,f(n/b^i)$$
Read the per-level work as a geometric series (Ch. 11):
| Per-level work… | Sum dominated by | Result |
|---|---|---|
| increases down the tree (ratio $>1$) | last term = leaves | $\Theta(n^E)$ |
| stays equal (ratio $=1$) | all $\log_b n$ terms | $\Theta(n^E \log n)$ |
| decreases down the tree (ratio $<1$) | first term = root | $\Theta(f(n))$ |
Method 2 — Master Theorem (the fast shortcut)
Compute $E = \log_b a$, then compare $f(n)$ to $n^{E}$:
| Case | Condition | Intuition | $T(n)$ |
|---|---|---|---|
| 1 | $f(n) = O(n^{E-\varepsilon})$, some $\varepsilon>0$ | $f$ polynomially smaller; leaves win | $\Theta(n^{E})$ |
| 2 | $f(n) = \Theta(n^{E})$ | same order; balanced | $\Theta(n^{E}\log n)$ |
| 3 | $f(n) = \Omega(n^{E+\varepsilon})$ AND $a f(n/b)\le c f(n)$, $c<1$ | $f$ polynomially larger; root wins | $\Theta(f(n))$ |
Decision procedure: (1) read $a, b, f$; (2) compute $E=\log_b a$ and $n^E$; (3) is $f$ polynomially smaller / equal / polynomially larger than $n^E$? → Case 1 / 2 / 3. Case 3 also requires the regularity check.
Memorize these five
| Recurrence | $E$ | Case | $T(n)$ | Algorithm |
|---|---|---|---|---|
| $T(n)=T(n/2)+\Theta(1)$ | 0 | 2 | $\Theta(\log n)$ | binary search, fast exponentiation |
| $T(n)=2T(n/2)+\Theta(n)$ | 1 | 2 | $\Theta(n\log n)$ | merge sort |
| $T(n)=2T(n/2)+\Theta(1)$ | 1 | 1 | $\Theta(n)$ | balanced tree traversal |
| $T(n)=3T(n/2)+\Theta(n)$ | $\log_2 3\approx 1.585$ | 1 | $\Theta(n^{\log_2 3})$ | Karatsuba multiplication |
| $T(n)=2T(n/2)+\Theta(n^2)$ | 1 | 3 | $\Theta(n^2)$ | root-heavy combine |
Merge sort & binary search
| Recurrence | Solution | Note | |
|---|---|---|---|
| Merge sort | $2T(n/2)+\Theta(n)$ | $\Theta(n\log n)$ | same in best/worst/avg case (data-independent split + merge); merge is linear (index sum $i+j$ rises by 1 per step) |
| Binary search | $T(n/2)+\Theta(1)$ | $\Theta(\log n)$ | $\le\lceil\log_2 n\rceil$ probes; $10^9$ elements → 30 probes |
Merge sort matches the $\Omega(n\log n)$ comparison-sort lower bound (Ch. 14) → asymptotically optimal.
Fibonacci (the anchor) — three speeds
| Method | Time | Exact? | Idea |
|---|---|---|---|
| naive recursion | $\Theta(\phi^n)$ (exponential) | yes | $T(n)=T(n-1)+T(n-2)+\Theta(1)$; recomputes subproblems |
| memoized / iterative | $\Theta(n)$ | yes | compute each $F_k$ once |
| matrix exponentiation | $O(\log n)$ | yes | square the matrix $M$ |
| Binet closed form | $O(1)$ symbolic | no (float rounding) | $F_n=\frac{\phi^n-\psi^n}{\sqrt5}$ |
The generating matrix (proved by induction): $$M=\begin{pmatrix}1&1\\1&0\end{pmatrix}, \qquad M^{n}=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}.$$ $F_n$ = top-right entry of $M^n$. Compute $M^n$ by exponentiation by squaring: $$M^n=\begin{cases}(M^{n/2})^2 & n\text{ even}\\ M\cdot(M^{(n-1)/2})^2 & n\text{ odd}\end{cases}\quad\Rightarrow\quad O(\log n)\text{ multiplies}.$$
Golden ratio: $\phi=\frac{1+\sqrt5}{2}\approx 1.618$, $\psi=\frac{1-\sqrt5}{2}\approx -0.618$;
$F_n=\Theta(\phi^n)$ (this is why naive recursion is exponential). Same squaring trick → mod_pow
for RSA (Ch. 23, 25).
When the Master Theorem does NOT apply
| Situation | Example | Use instead |
|---|---|---|
| subtractive (size $n-1$, not $n/b$) | $T(n)=T(n-1)+T(n-2)$; $T(n)=T(n-1)+\Theta(n)$ | characteristic equation (Ch. 18) / unroll → $\Theta(n^2)$ |
| only a log gap (Case 2/3 blind spot) | $T(n)=2T(n/2)+n\log n$ | recursion tree → $\Theta(n\log^2 n)$; or extended Case 2: $\Theta(n^E\log^k n)\to\Theta(n^E\log^{k+1}n)$ |
| unequal subproblem sizes | $T(n)=T(n/3)+T(2n/3)+\Theta(n)$ | Akra–Bazzi → $\Theta(n\log n)$ |
| pathological / non-poly $f$ | $f(n)=n/\log n$ | recursion tree or substitution |
Substitution method (universal backstop): guess the bound (draw a tree), then prove by induction (Ch. 6) — assume it for inputs $< n$, plug into the recurrence, verify at $n$.
Common pitfalls
- "Polynomially" ≠ "merely." Cases 1 & 3 need a factor of $n^{\varepsilon}$ gap, not a $\log$ gap. $n\log n$ is not polynomially larger than $n$.
- Forgetting regularity in Case 3. "$f$ is bigger" is not enough — check $a f(n/b)\le c f(n)$, $c<1$.
- Counting pieces, not calls. $a$ = recursive calls made. Binary search cuts in half but $a=1$ (recurses on one side); merge sort $a=2$ (sorts both).
- Binet for large $n$. Floating-point $\phi^n$ rounds wrong eventually — use the integer matrix method.
- Assuming all recurrences are divide-and-conquer. Subtractive recurrences need Chapter 18's tools.
Toolkit additions (dmtoolkit/recurrences.py)
| Function | Signature | Does | Cost |
|---|---|---|---|
| (Ch. 18) | solve_linear(coeffs, inits, n) |
solve a linear recurrence | — |
| this ch. | fib(n) |
$n$th Fibonacci by matrix exponentiation | $O(\log n)$, exact |
fib(10) # -> 55
[fib(k) for k in range(10)] # -> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
Same squaring loop → mod_pow(b, e, m) (Ch. 23) → fast RSA (Ch. 25 capstone).