The master theorem solves recurrences of the form
T(n) = a·T(n/b) + f(n)
where a divide-and-conquer algorithm makes a recursive calls on inputs of size n/b and does f(n) work to split and combine. You don't need to unroll anything: compare f(n) with one number and read off the answer.
The one comparison
Compute the critical exponent log_b(a). The recursion alone produces n^(log_b a) leaves of work; the question is whether f(n) is smaller, about equal, or larger.
| Case | When | Answer |
|---|---|---|
| 1 | f(n) grows polynomially slower than n^(log_b a) | T(n) = Θ(n^(log_b a)) |
| 2 | f(n) = Θ(n^(log_b a) · logᵏ n) | T(n) = Θ(n^(log_b a) · logᵏ⁺¹ n) |
| 3 | f(n) grows polynomially faster, and a·f(n/b) ≤ c·f(n) for some c < 1 | T(n) = Θ(f(n)) |
With k = 0, case 2 is the familiar "equal" case: Θ(n^(log_b a) · log n). The extended version with k > 0 is what solves recurrences like 2T(n/2) + n log n, which the basic three cases can't.
Ten solved examples
| Recurrence | a, b | log_b a | f(n) | Case | T(n) |
|---|---|---|---|---|---|
| T(n) = 2T(n/2) + n (merge sort) | 2, 2 | 1 | n | 2 | Θ(n log n) |
| T(n) = T(n/2) + 1 (binary search) | 1, 2 | 0 | 1 | 2 | Θ(log n) |
| T(n) = 3T(n/2) + n (Karatsuba) | 3, 2 | 1.585 | n | 1 | Θ(n^1.585) |
| T(n) = 7T(n/2) + n² (Strassen) | 7, 2 | 2.807 | n² | 1 | Θ(n^2.807) |
| T(n) = 8T(n/2) + n² | 8, 2 | 3 | n² | 1 | Θ(n³) |
| T(n) = 4T(n/2) + n | 4, 2 | 2 | n | 1 | Θ(n²) |
| T(n) = 2T(n/2) + n² | 2, 2 | 1 | n² | 3 | Θ(n²) |
| T(n) = T(n/3) + n | 1, 3 | 0 | n | 3 | Θ(n) |
| T(n) = 3T(n/4) + n log n | 3, 4 | 0.792 | n log n | 3 | Θ(n log n) |
| T(n) = 2T(n/2) + n log n | 2, 2 | 1 | n log n | 2 (k = 1) | Θ(n log² n) |
Two worked in full
Strassen, T(n) = 7T(n/2) + n². log₂ 7 ≈ 2.807. f(n) = n² is polynomially smaller than n^2.807 (by a factor of n^0.807), so case 1 applies: the leaves dominate, and T(n) = Θ(n^log₂7) ≈ Θ(n^2.807). That is why Strassen beats the ordinary Θ(n³) matrix multiplication (the 8T(n/2) + n² row).
T(n) = 2T(n/2) + n². log₂ 2 = 1, and f(n) = n² is polynomially larger than n¹. Check the regularity condition: a·f(n/b) = 2·(n/2)² = n²/2 ≤ ½·n², so c = ½ works. Case 3: the top level dominates, T(n) = Θ(n²).
When the master theorem doesn't apply
- The subproblems aren't equal sizes, e.g. T(n) = T(n/3) + T(2n/3) + n. Use a recursion tree or the Akra–Bazzi method.
- The recurrence subtracts instead of divides, e.g. T(n) = T(n − 1) + n (that's Θ(n²), by unrolling).
- a < 1, or b ≤ 1: not a divide-and-conquer recurrence.
- f(n) falls between the cases in the basic theorem, e.g. 2T(n/2) + n/log n. Neither the basic nor the extended version above covers that one.
Common mistakes
- Comparing f(n) with n^a or n^b instead of n^(log_b a).
- Calling it case 3 without checking regularity. For ordinary polynomial f(n) it always holds, but say so.
- Forgetting the extra log in case 2. f(n) = n with log_b a = 1 gives n log n, not n.
Try it
The master theorem calculator takes a, b and f(n) = nᶜ · logᵏ n, shows the critical exponent, picks the case and explains why, including the extended case-2 form for n log n terms.
Use the Huffman Coding Calculator to work through a related algorithms exercise. For a related walkthrough, read Huffman Coding Example, Step by Step.