Foundation · Module 1 · Lesson 5
Recurrences & Master Theorem
Analyze divide-and-conquer algorithms.
Lesson 5 of 123
1d streakDetailed theory
A recurrence describes the cost of a recursive algorithm in terms of smaller inputs. A recursion tree, substitution, or the Master Theorem can turn that description into an asymptotic bound.
By the end, you can
- Translate recursive code into T(n) = subproblems + local work.
- Solve common recurrences with a recursion tree.
- Apply the Master Theorem only when its required form fits.
Vocabulary
Definitions with concrete meaning
Recurrence
An equation that defines T(n) using costs on smaller inputs.
Base case
The smallest input whose cost is bounded by a constant.
Master form
T(n) = aT(n/b) + f(n), where a is subproblem count, n/b is subproblem size, and f(n) is non-recursive work.
Critical term
n^(log_b a), the total leaf-growth scale used to compare against f(n).
Rules to apply
- 1Include recursive calls and all local work such as partitioning, copying, or combining.
- 2In a recursion tree: number of nodes at a level × work per node = level cost.
- 3Master case 1: f(n) is polynomially smaller than n^(log_b a), so leaves dominate.
- 4Master case 2: f(n) matches the critical term up to logarithmic factors, adding a log factor.
- 5Master case 3: f(n) is polynomially larger and regularity holds, so root-level work dominates.
- 6The basic Master Theorem does not directly handle unequal subproblem sizes such as T(n/3) + T(2n/3).
Worked example 1
Binary search recurrence
One recursive call processes half the range, with constant local work.
- 1
Write the recurrence
T(n) = T(n/2) + Θ(1), with T(1) = Θ(1).
- 2
Count levels
After k halvings, n / 2ᵏ = 1, so k = log₂ n.
- 3
Sum level work
Each level costs Θ(1), across Θ(log n) levels.
T(n) = Θ(log n).
Worked example 2
Merge sort with Master Theorem
Two half-size recursive calls are followed by a linear merge.
- 1
Identify parameters
T(n) = 2T(n/2) + Θ(n), so a = 2, b = 2, and f(n) = Θ(n).
- 2
Compute critical term
n^(log_b a) = n^(log₂2) = n.
- 3
Compare
f(n) = Θ(n) matches the critical term, which is Master case 2.
T(n) = Θ(n log n).
Worked example 3
A root-dominated recurrence
Solve T(n) = 2T(n/2) + Θ(n²).
- 1
Critical term
n^(log₂2) = n.
- 2
Compare local work
f(n) = n² is polynomially larger than n.
- 3
Check regularity
2f(n/2) = 2(n/2)² = n²/2 ≤ c n² for c = 1/2.
Master case 3 applies, so T(n) = Θ(n²).
Comparison table
Master Theorem quick reference
Let p = log_b a and compare f(n) with nᵖ.
| Case | Comparison | Result | Intuition |
|---|---|---|---|
| 1 | f(n) = O(n^(p−ε)) | Θ(nᵖ) | Leaves dominate |
| 2 | f(n) = Θ(nᵖ logᵏn) | Θ(nᵖ logᵏ⁺¹n) | Levels balance |
| 3 | f(n) = Ω(n^(p+ε)) + regularity | Θ(f(n)) | Root work dominates |
Check your understanding
1What recurrence models two recursive calls on n/2 plus a full scan?
T(n) = 2T(n/2) + Θ(n).
2Why is T(n) = T(n−1) + n not a basic Master-Theorem recurrence?
Its subproblem size is n−1, not n/b for a constant b > 1.
3What does a recursion tree count at each level?
Number of calls at that level multiplied by the non-recursive work per call.
Cost Model
Complexity & Trade-offs
When to use it
- Analyzing divide-and-conquer, tree recursion, and recursive search.
- Explaining binary search, merge sort, and many geometric subdivisions.
- Comparing whether leaves, all levels, or root work dominates.
Common mistakes
- Forgetting partition, merge, slicing, or copying work outside recursive calls.
- Applying the Master Theorem to a recurrence that does not match its form.
- Ignoring recursion-stack or temporary-buffer space after solving time.
Practice prompts
- Solve T(n) = 4T(n/2) + n.
- Draw the recursion tree for T(n) = 2T(n/2) + n.
- Explain why T(n) = T(n−1) + n solves to Θ(n²).
Mastery check