Recurrences
A recursive algorithm's cost is written in terms of itself. Unroll it until you hit the base case, then add up what you wrote down.
Recursive substitution (also called the iteration method) means: plug the recurrence into itself a few times, spot the pattern, stop when the input size reaches the base case, and sum.
The four moves
- Choose n to be a power of the divisor. If the recurrence divides by \(b\), take \(n=b^k\). Then \(n/b^k=1\) exactly, which tells you where to stop, and \(k=\log_b n\).
- Expand two or three times and keep the terms unsimplified so the pattern stays visible.
- Write the general term after \(i\) expansions: \(a^i\,T(n/b^i)+\sum_{m=0}^{i-1}a^m f(n/b^m)\).
- Set \(i=k\), plug in the base case, and evaluate the sum. It is almost always a geometric series.
Worked example: \(T(n)=2T(n/2)+n\), \(T(1)=1\)
Let \(n=2^k\). Expanding:
\[ T(n)=2T(n/2)+n=4T(n/4)+2n=8T(n/8)+3n=\cdots=2^iT(n/2^i)+i\,n. \]
Each level contributes \(2^m\cdot n/2^m=n\). At \(i=k\): \(T(n)=2^k\cdot1+kn=n+n\log_2 n\). So \(T(n)=\Theta(n\log n)\).
Worked example 2: \(T(n)=3T(n/2)+n\), \(T(1)=1\)
Level \(m\) has \(3^m\) calls of size \(n/2^m\), so it costs \(3^m\cdot n/2^m=n(3/2)^m\). The costs now grow with depth, giving a geometric series with ratio \(3/2\):
\[ T(n)=3^k+n\sum_{m=0}^{k-1}\left(\tfrac32\right)^m=3^k+2n\left(\left(\tfrac32\right)^k-1\right)=3^k+2\cdot3^k-2n=3\cdot3^k-2n. \]
Since \(3^k=n^{\log_2 3}\), \(T(n)=3n^{\log_2 3}-2n=\Theta(n^{1.58})\). Check: \(T(2)=3+2=5\) and the formula gives \(9-4=5\).
Reading the pattern
- Level totals constant: work is spread evenly. Total = (cost per level) × (number of levels).
- Level totals growing: the bottom dominates. Think leaves.
- Level totals shrinking: the top dominates. Think root.
Always check your closed form by computing the first few values both ways: from the recurrence, and from your formula.
Common slips: forgetting that the cost term itself changes size at each level (\(f(n/b^m)\), not \(f(n)\)), using the wrong ratio in the geometric series, and leaving off the base-case term \(a^k\,T(1)\).
Geometric series you will keep needing
\[ \sum_{m=0}^{k-1} r^m=\frac{r^k-1}{r-1}\quad(r\neq1) \]
The trick \(n\,r^k=a^k\) when \(n=b^k\) and \(r=a/b\) turns many of these into clean powers.