15.2 Master Theorem
Many divide-and-conquer algorithms produce recurrences of the form \[ T(n)=aT\left(\frac{n}{b}\right)+f(n) \]
15.2 Master Theorem
Problem
Many divide-and-conquer algorithms produce recurrences of the form
$$ T(n)=aT\left(\frac{n}{b}\right)+f(n) $$
where:
- (a) is the number of recursive subproblems.
- (n/b) is the size of each subproblem.
- (f(n)) is the non-recursive work performed at each call.
For simple recurrences, recursion trees provide an intuitive solution. For larger algorithms, repeatedly constructing trees becomes tedious.
Is there a systematic way to solve an entire class of divide-and-conquer recurrences?
Solution
Use the Master Theorem.
The Master Theorem provides asymptotic bounds for recurrences of the form:
$$ T(n)=aT\left(\frac{n}{b}\right)+f(n) $$
with:
$$ a \ge 1 $$
and
$$ b > 1 $$
The theorem compares two quantities:
- Work generated by recursive calls.
- Work performed outside recursion.
The critical quantity is:
$$ n^{\log_b a} $$
This value represents the total contribution of the recursive structure itself.
genui{"math_block_widget_always_prefetch_v2":{"content":"n^{\log_b a}"}}
Once (f(n)) is compared against this value, the solution follows directly.
Understanding the Critical Term
Consider:
$$ T(n)=2T(n/2) $$
The recursion tree doubles the number of nodes while halving problem size.
At depth (k):
$$ 2^k $$
nodes exist.
The recursion terminates after:
$$ \log_2 n $$
levels.
The total number of leaves becomes:
$$ 2^{\log_2 n}=n $$
This leaf count generalizes to:
$$ n^{\log_b a} $$
for arbitrary (a) and (b).
This quantity serves as the dividing line between the three Master Theorem cases.
Case 1: Recursive Work Dominates
If
$$ f(n)=O\left(n^{\log_b a-\varepsilon}\right) $$
for some positive constant (\varepsilon),
then recursive work dominates.
The solution becomes:
$$ T(n)=\Theta\left(n^{\log_b a}\right) $$
Example
$$ T(n)=4T(n/2)+n $$
Compute:
$$ n^{\log_2 4}=n^2 $$
Compare:
$$ f(n)=n $$
Since
$$ n=o(n^2) $$
Case 1 applies.
Result:
$$ T(n)=\Theta(n^2) $$
The recursive structure produces more work than the combining step.
Case 2: Balanced Work
If
$$ f(n)=\Theta\left(n^{\log_b a}\right) $$
then recursive work and local work contribute equally.
The solution becomes:
$$ T(n)=\Theta\left(n^{\log_b a}\log n\right) $$
Example
$$ T(n)=2T(n/2)+n $$
Compute:
$$ n^{\log_2 2}=n $$
Compare:
$$ f(n)=n $$
The functions match exactly.
Case 2 applies.
Result:
$$ T(n)=\Theta(n\log n) $$
This is the classic merge sort recurrence.
Case 3: Local Work Dominates
If
$$ f(n)=\Omega\left(n^{\log_b a+\varepsilon}\right) $$
and the regularity condition holds,
then local work dominates.
The solution becomes:
$$ T(n)=\Theta(f(n)) $$
Example
$$ T(n)=2T(n/2)+n^2 $$
Compute:
$$ n^{\log_2 2}=n $$
Compare:
$$ f(n)=n^2 $$
Since
$$ n^2 $$
grows faster than
$$ n $$
Case 3 applies.
Result:
$$ T(n)=\Theta(n^2) $$
The combining work overwhelms the recursive work.
Master Theorem Summary
| Comparison | Result |
|---|---|
| (f(n)) smaller than (n^{\log_b a}) | (\Theta(n^{\log_b a})) |
| (f(n)) equal to (n^{\log_b a}) | (\Theta(n^{\log_b a}\log n)) |
| (f(n)) larger than (n^{\log_b a}) | (\Theta(f(n))) |
Most divide-and-conquer algorithms encountered in practice fall into one of these categories.
Example: Merge Sort
Recurrence:
$$ T(n)=2T(n/2)+n $$
Critical term:
$$ n^{\log_2 2}=n $$
Work matches.
Case 2.
Result:
$$ T(n)=\Theta(n\log n) $$
Example: Binary Search
Recurrence:
$$ T(n)=T(n/2)+1 $$
Critical term:
$$ n^{\log_2 1}=1 $$
Work matches.
Case 2.
Result:
$$ T(n)=\Theta(\log n) $$
Example: Strassen Multiplication
Recurrence:
$$ T(n)=7T(n/2)+n^2 $$
Critical term:
$$ n^{\log_2 7} $$
approximately:
$$ n^{2.807} $$
Since
$$ n^2 $$
grows more slowly than
$$ n^{2.807} $$
Case 1 applies.
Result:
$$ T(n)=\Theta(n^{2.807}) $$
This improvement over classical matrix multiplication is the key insight behind Strassen's algorithm.
When the Master Theorem Fails
Not every recurrence fits the theorem.
Unequal Subproblems
$$ T(n)=T(n/3)+T(2n/3)+n $$
Subproblem sizes differ.
The standard theorem does not apply.
Non-Polynomial Terms
$$ T(n)=2T(n/2)+n\log n $$
The comparison becomes more subtle.
Extended forms may be needed.
Variable Branching Factors
$$ T(n)=nT(n/2)+n $$
The coefficient depends on (n).
The theorem cannot be applied directly.
Recursive Terms with Offsets
$$ T(n)=T(n/2)+T(n/2+1) $$
Special analysis is required.
Recipe
Given:
$$ T(n)=aT(n/b)+f(n) $$
follow these steps:
- Compute (n^{\log_b a}).
- Compare (f(n)) against that term.
- Determine whether (f(n)) is smaller, equal, or larger.
- Apply the corresponding Master Theorem case.
- Verify that theorem assumptions hold.
Most recurrences can be solved in less than a minute once this process becomes familiar.
Discussion
The recursion tree from the previous section provides intuition. The Master Theorem transforms that intuition into a reusable analytical tool. Instead of summing work level by level, we compare local work against the natural growth generated by the recursive structure.
For algorithm designers, the most important skill is recognizing the significance of the critical term (n^{\log_b a}). Once this value is identified, the asymptotic behavior of many divide-and-conquer algorithms becomes immediately apparent. The remaining sections of this chapter repeatedly use this theorem to analyze increasingly sophisticated algorithms, from sorting and selection to matrix multiplication and geometric search.