Solving Recurrences: Substitution & the Master Theorem

Algorithms & Complexity

Chapter 6 · Solving Recurrences: Substitution & the Master Theorem

Chapter 5 set up merge sort's own recurrence, T(n) = 2T(n/2) + O(n), and left it unsolved. This chapter solves it two ways: the slow, honest way (full substitution), and the fast way every divide-and-conquer recurrence of this shape actually gets solved in practice — the Master Theorem.

Solving by Substitution — Merge Sort's Recurrence, Fully Unrolled

Starting from T(n) = 2T(n/2) + cn, repeatedly substituting the recurrence into itself:

Step	Expression
1 level	`2T(n/2) + cn`
2 levels	`4T(n/4) + 2cn`
3 levels	`8T(n/8) + 3cn`
k levels	`2ᵏT(n/2ᵏ) + k·cn`

The pattern bottoms out when n/2ᵏ = 1, i.e. k = log₂n. Substituting: T(n) = 2^(log₂n)·T(1) + (log₂n)·cn = n·T(1) + cn·log₂n — Θ(n log n).

Verified directly (c=1, T(1)=1):

n	T(n)	n + n·log₂n
4	12	12.0
8	32	32.0
16	80	80.0

The Master Theorem — A Fast-Path Formula

For any recurrence of the shape T(n) = aT(n/b) + f(n), compare f(n) against n^(log_b a):

Case	Condition	Result
1	`f(n)` grows slower than `n^(log_b a)`	`T(n) = Θ(n^(log_b a))` — the recursion dominates
2	`f(n)` grows at the same rate as `n^(log_b a)`	`T(n) = Θ(n^(log_b a) · log n)` — perfectly balanced
3	`f(n)` grows faster than `n^(log_b a)`	`T(n) = Θ(f(n))` — the non-recursive work dominates

Applying It: Merge Sort, Confirmed Instantly

T(n) = 2T(n/2) + cn: a=2, b=2, f(n) = Θ(n). n^(log_b a) = n^(log₂2) = n¹ = n. Since f(n) = Θ(n) matches n^(log_b a) = n exactly — Case 2: T(n) = Θ(n · log n). Matches the full substitution above exactly, without needing to unroll anything.

Applying It: Binary Search, Confirmed Against Chapter 1

T(n) = T(n/2) + O(1): a=1, b=2, f(n) = Θ(1) = Θ(n⁰). n^(log_b a) = n^(log₂1) = n⁰ = 1. f(n) matches — Case 2: T(n) = Θ(n⁰ · log n) = Θ(log n). Exactly Chapter 1's own opening figure, now derived formally rather than just quoted.

Applying It: A Genuine Case 1 — When Recursion Dominates

T(n) = 4T(n/2) + n: a=4, b=2, f(n) = Θ(n). n^(log_b a) = n^(log₂4) = n². Since f(n) = n grows strictly slower than n² — Case 1: T(n) = Θ(n²), the recursive branching dominates entirely; the linear extra work barely matters.

Verified by watching the ratio converge

Computing T(n) directly and dividing by n²: at n=8, ratio ≈ 1.875; at n=32, ≈ 1.969; at n=64, ≈ 1.984 — steadily converging toward a constant, exactly Chapter 2's own signature of a correct Θ classification, not drifting toward 0 or infinity.

Solving Chapter 5's Own Unsolved Exercise

Chapter 5's Exercise 2 asked only to write T(n) = 3T(n/3) + O(n), promising the Master Theorem would solve it here. a=3, b=3, f(n) = Θ(n). n^(log_b a) = n^(log₃3) = n¹ = n. f(n) matches — Case 2: T(n) = Θ(n log n), the exact same class as merge sort, despite splitting into three pieces instead of two.

The Master Theorem in Code

import math

def master_theorem_exponent(a, b):
    return math.log(a, b)   # n^(log_b a)

print(master_theorem_exponent(2, 2))  # 1.0 -- merge sort: n^1 = n
print(master_theorem_exponent(1, 2))  # 0.0 -- binary search: n^0 = 1
print(master_theorem_exponent(4, 2))  # 2.0 -- Case 1 example: n^2
print(master_theorem_exponent(3, 3))  # 1.0 -- Chapter 5's own exercise: n^1 = n

Hands-On Exercises

Exercise 1

For T(n) = 4T(n/2) + n, this chapter's own Case 1 example, verify by direct substitution/unrolling that T(8) = 120 (with T(1) = 1), and confirm this is consistent with the Master Theorem's Θ(n²) prediction (compare 120 to 8² = 64 and note the constant-factor gap is expected).

📄 View solution

Exercise 2

Apply the Master Theorem to T(n) = T(n/2) + n². Compute a, b, n^(log_b a), compare it to f(n) = n², identify which case applies, and state the resulting Θ class.

📄 View solution

Exercise 3

A recursive algorithm makes 8 recursive calls, each on a half-sized (n/2) subproblem, plus O(n²) non-recursive work. Write its recurrence, apply the Master Theorem, and state the resulting Θ class.

📄 View solution

Chapter 6 Quick Reference

Substitution: unroll T(n) = 2T(n/2) + cn level by level until it bottoms out at k = log₂n levels — gives Θ(n log n)
Master Theorem: for T(n) = aT(n/b) + f(n), compare f(n) to n^(log_b a) — three cases, whichever grows faster (or ties) wins
Case 2 (tie) confirms both merge sort (Θ(n log n)) and binary search (Θ(log n)) without unrolling by hand
Case 1 (recursion dominates) gives Θ(n²) for T(n)=4T(n/2)+n, verified by a ratio converging to a constant
Chapter 5's own unresolved 3T(n/3)+O(n) resolves to Θ(n log n) — Case 2 again, just with a different a and b
Next chapter: Common complexity classes in practice — searching and sorting