Solving Recurrences
Motivation
Divide-and-conquer algorithms naturally produce recurrence relations for their running time: solve a few subproblems of size \(n/b\) at cost \(T(n/b)\) each, then spend \(f(n)\) to combine. To compare such algorithms — is mergesort faster than insertion sort? is Karatsuba multiplication faster than schoolbook? — we need a way to convert recurrences into closed-form bounds (Cormen et al. 2009; Kleinberg and Tardos 2005).
Three techniques cover virtually every recurrence we encounter in this course: substitution (guess and prove), the recursion tree (visualize and sum), and the master theorem (canned answers for the most common form).
Standard form
The divide-and-conquer recurrence is \[ T(n) = a \, T(n/b) + f(n), \] where \(a \ge 1\) subproblems are recursively solved, each on input of size \(n/b\) with \(b > 1\), and \(f(n)\) is the non-recursive cost (the divide and combine work). The base case is \(T(1) = \Theta(1)\).
Method 1: Substitution
Guess a form for \(T(n)\) and prove it by induction.
Example: \(T(n) = 2T(n/2) + n\) (mergesort). Guess \(T(n) \le c \, n \log_2 n\) for some constant \(c\). By induction on \(n\) (assuming the bound for \(n/2\)): \[ T(n) \le 2 \cdot c \cdot (n/2) \log_2(n/2) + n = c \, n (\log_2 n - 1) + n = c \, n \log_2 n + (1 - c) n. \] For \(c \ge 1\) and large enough \(n_0\), this is \(\le c \, n \log_2 n\). A matching lower bound proves \(T(n) = \Theta(n \log n)\).
Substitution is most useful when the answer is already known or guessable. Watch out for “absorbing” lower-order terms: trying to prove \(T(n) \le c \, n \log n\) may fail because of an additive constant; it is often easier to prove \(T(n) \le c \, n \log n - d\) for some additional constant \(d\).
Method 2: Recursion tree
Draw the recursion as a tree: the root has cost \(f(n)\), and each node at depth \(i\) has \(a^i\) copies, each contributing \(f(n / b^i)\).
Example: \(T(n) = 2T(n/2) + n\). - Level 0: cost \(n\). - Level 1: \(2\) nodes, each cost \(n/2\), total \(n\). - Level \(i\): \(2^i\) nodes, each cost \(n/2^i\), total \(n\). - Number of levels: \(\log_2 n\).
Total: \(\sum_i n = n \log_2 n = \Theta(n \log n)\).
Diagram: cost per level for \(T(n) = 2 T(n/2) + n\)
Example: \(T(n) = T(n/2) + 1\) (binary search). - Each level contributes \(1\), and there are \(\log_2 n\) levels. - Total: \(\Theta(\log n)\).
The recursion-tree picture also makes it clear where the cost lives. In mergesort, every level is equally expensive (the work is “balanced” between root and leaves). In binary search, almost all the cost is at the leaves. In a recurrence like \(T(n) = 2T(n/2) + n^2\), the root dominates.
Method 3: The master theorem
For the recurrence \(T(n) = a T(n/b) + f(n)\) with \(a \ge 1\), \(b > 1\), the master theorem compares \(f(n)\) to \(n^{\log_b a}\) (proof):
- Case 1 (leaves dominate): if \(f(n) = O(n^{\log_b a - \epsilon})\) for some \(\epsilon > 0\), then \(T(n) = \Theta(n^{\log_b a})\).
- Case 2 (balanced): if \(f(n) = \Theta(n^{\log_b a} \log^k n)\) for some \(k \ge 0\), then \(T(n) = \Theta(n^{\log_b a} \log^{k+1} n)\).
- Case 3 (root dominates): if \(f(n) = \Omega(n^{\log_b a + \epsilon})\) for some \(\epsilon > 0\) and the regularity condition \(a f(n/b) \le c f(n)\) holds for some \(c < 1\), then \(T(n) = \Theta(f(n))\).
The exponent \(\log_b a\) is the critical exponent — it is the rate at which the number of leaves grows, namely \(n^{\log_b a}\).
Worked examples
| Recurrence | Critical exponent \(\log_b a\) | \(f(n)\) | Master case | \(T(n)\) |
|---|---|---|---|---|
| \(T(n) = 2T(n/2) + n\) (mergesort) | \(1\) | \(n\) | Case 2, \(k = 0\) | \(\Theta(n \log n)\) |
| \(T(n) = 2T(n/2) + 1\) | \(1\) | \(1\) | Case 1 | \(\Theta(n)\) |
| \(T(n) = T(n/2) + 1\) (binary search) | \(0\) | \(1\) | Case 2 | \(\Theta(\log n)\) |
| \(T(n) = 3T(n/2) + n\) (Karatsuba) | \(\log_2 3 \approx 1.585\) | \(n\) | Case 1 | \(\Theta(n^{\log_2 3})\) |
| \(T(n) = 7T(n/2) + n^2\) (Strassen) | \(\log_2 7 \approx 2.807\) | \(n^2\) | Case 1 | \(\Theta(n^{\log_2 7})\) |
| \(T(n) = 2T(n/2) + n^2\) | \(1\) | \(n^2\) | Case 3 | \(\Theta(n^2)\) |
| \(T(n) = T(n-1) + 1\) | — | — | (not master form) | \(\Theta(n)\) |
| \(T(n) = T(n-1) + n\) (selection sort) | — | — | (not master form) | \(\Theta(n^2)\) |
Example: deriving a recurrence from pseudocode
Given a recursive procedure, identify the three ingredients: number of recursive calls, size of each subproblem, and cost of the non-recursive work.
procedure mystery(A, lo, hi):
if hi - lo < 1: return
mid = (lo + hi) / 2
mystery(A, lo, mid) # first recursive call, size n/2
mystery(A, mid+1, hi) # second recursive call, size n/2
for i = lo to hi: # combine: O(n) work
process(A[i])Reading off the recurrence (with \(n = hi - lo + 1\)):
- Two recursive calls, each on a subarray of size \(n/2\): contributes \(2T(n/2)\).
- The loop runs exactly \(n\) times: contributes \(\Theta(n)\).
\[T(n) = 2T(n/2) + \Theta(n), \qquad T(1) = \Theta(1).\]
Master theorem Case 2 (\(\log_2 2 = 1\), \(f(n) = \Theta(n^1)\), \(k=0\)): \(T(n) = \Theta(n \log n)\).
Contrast with a procedure that does \(\Theta(n^2)\) combine work (say, a nested loop from lo to hi):
\[T(n) = 2T(n/2) + \Theta(n^2).\]
Now \(f(n) = n^2 = \Omega(n^{1+\epsilon})\) for \(\epsilon = 1\), the regularity condition holds, and Master Case 3 gives \(T(n) = \Theta(n^2)\).
Beyond the master theorem
The master theorem covers \(T(n) = a T(n/b) + f(n)\) with constant \(a, b\). Recurrences outside this form (subtractive, e.g., \(T(n) = T(n-1) + n\); uneven splits, e.g., \(T(n) = T(n/3) + T(2n/3) + n\); or the Akra–Bazzi generalization) require other tools — often substitution or recursion trees, or in the Akra–Bazzi case a closed-form integral.
Pitfalls
- The regularity condition in master Case 3 is real. Without it, the master theorem does not apply.
- Floors and ceilings (\(n/2\) vs. \(\lceil n/2 \rceil\)) do not change the asymptotic answer for any standard recurrence; we suppress them throughout.
- Critical exponent ties: when \(f(n) = \Theta(n^{\log_b a})\) exactly, you are in Case 2 with \(k = 0\) — total cost is \(\Theta(n^{\log_b a} \log n)\), not just \(\Theta(n^{\log_b a})\).