Master Theorem: A Complete Guide
Learn the Master Theorem to solve recurrence relations quickly. Understand its three cases with step-by-step examples and complexity analysis.
1. Why Do We Need the Master Theorem?
Consider a recursive algorithm that divides a problem into smaller subproblems, solves them recursively, and performs some additional work.
Its running time may be expressed as:
\[
T(n)=aT\left(\frac nb\right)+f(n)
\]
Where:
- \(a\) = number of recursive subproblems.
- \(n/b\) = size of each subproblem.
- \(f(n)\) = additional work outside the recursive calls.
- \(T(n)\) = total running time.
Solving such recurrences using substitution or recursion trees can be time-consuming.
The Master Theorem provides a direct method to determine the asymptotic complexity of many recurrences of this form.
2. The General Form
The Master Theorem applies to recurrences of the form:
\[
T(n)=aT\left(\frac nb\right)+f(n)
\]
where:
- \(a\geq1\)
- \(b>1\)
- \(f(n)\) is a non-negative function.
The most important step is to calculate:
\[
n^{\log_b a}
\]
This represents the growth associated with the recursive structure of the algorithm.
We then compare \(f(n)\) with \(n^{\log_b a}\) to determine which part dominates the total work.
3. The Three Cases of the Master Theorem
Case 1: Recursive Work Dominates
If the additional work grows polynomially slower than the recursive contribution:
\[
f(n)=O\left(n^{\log_ba-\varepsilon}\right)
\]
for some constant \(\varepsilon>0\), then:
\[
\boxed{T(n)=\Theta\left(n^{\log_ba}\right)}
\]
In simple terms, the recursive work dominates the total complexity.
Example
Consider:
\[
T(n)=2T\left(\frac n2\right)+1
\]
Here:
\[
a=2,\qquad b=2,\qquad f(n)=1
\]
Calculate:
\[
n^{\log_2 2}=n
\]
Since the additional work is constant, it grows slower than (n).
Therefore, Case 1 applies.
\[
\boxed{T(n)=\Theta(n)}
\]
This recurrence is similar to the recursive structure of Binary Search, whose complexity is logarithmic in the actual search process when only one subproblem is followed. Here, however, the recurrence has two recursive calls, so the total complexity is linear.
Case 2: Both Contributions Are Balanced
If the additional work grows at the same asymptotic rate as the recursive contribution:
\[
f(n)=\Theta\left(n^{\log_ba}\log^k n\right)
\]
where \(k\geq0\), then:
\[
\boxed{T(n)=\Theta\left(n^{\log_ba}\log^{k+1}n\right)}
\]
In simple terms, both contributions are balanced, and an additional logarithmic factor appears.
Example
Consider Merge Sort:
\[
T(n)=2T\left(\frac n2\right)+n
\]
Here:
\[
a=2,\qquad b=2,\qquad f(n)=n
\]
Calculate:
\[
n^{\log_2 2}=n
\]
Since:
\[
f(n)=\Theta(n)
\]
Case 2 applies with (k=0).
Therefore:
\[
T(n)=\Theta(n\log n)
\]
This is the complexity of Merge Sort.
Case 3: Additional Work Dominates
If the additional work grows polynomially faster than the recursive contribution:
\[
f(n)=\Omega\left(n^{\log_ba+\varepsilon}\right)
\]
for some constant (\varepsilon>0), and the regularity condition is satisfied:
\[
af\left(\frac nb\right)\leq cf(n)
\]
for some constant \(c<1\) and sufficiently large \(n\), then:
\[
\boxed{T(n)=\Theta(f(n))}
\]
In simple terms, the additional work dominates the total complexity.
Example
Consider:
\[
T(n)=2T\left(\frac n2\right)+n^2
\]
Here:
\[
a=2,\qquad b=2,\qquad f(n)=n^2
\]
Calculate:
\[
n^{\log_2 2}=n
\]
Since \(n^2\) grows polynomially faster than \(n\), Case 3 applies.
The regularity condition is also satisfied:
\[
2\left(\frac n2\right)^2
=\frac{n^2}{2}
\leq\frac12n^2
\]
Therefore:
\[
\boxed{T(n)=\Theta(n^2)}
\]
4. Summary of the Three Cases
Let:
\[
T(n)=aT\left(\frac nb\right)+f(n)
\]
and compare \(f(n)\) with:
\[
n^{\log_ba}
\]
| Case | Condition | Result |
|---|---|---|
| Case 1 | \(f(n)\) grows polynomially slower | \(\Theta(n^{\log_ba})\) |
| Case 2 | \(f(n)\) matches the recursive growth, with logarithmic factors | \(\Theta(n^{\log_ba}\log^{k+1}n)\) |
| Case 3 | \(f(n)\) grows polynomially faster and regularity condition holds | \(\Theta(f(n))\) |
5. How to Apply the Master Theorem
Whenever you are given a recurrence:
Step 1: Identify (a), (b), and (f(n)).
Step 2: Calculate:
\[
n^{\log_ba}
\]
Step 3: Compare (f(n)) with this function.
Step 4: Determine which case applies.
Step 5: Write the resulting complexity.
Quick Example
Solve:
\[
T(n)=4T\left(\frac n2\right)+n
\]
Identify:
\[
a=4,\qquad b=2,\qquad f(n)=n
\]
Calculate:
\[
n^{\log_2 4}=n^2
\]
Since (n) grows polynomially slower than \(n^2\), Case 1 applies.
Therefore:
\[
\boxed{T(n)=\Theta(n^2)}
\]
6. Limitations of the Master Theorem
The Master Theorem is useful, but it cannot solve every recurrence.
It generally applies to recurrences of the form:
\[
T(n)=aT\left(\frac nb\right)+f(n)
\]
It may not directly apply when:
- Subproblem sizes are unequal, such as \(T(n)=T(n/3)+T(2n/3)+n\).
- The recurrence does not follow the standard form.
- The function \(f(n)\) does not satisfy any of the three cases.
In such situations, other techniques such as the Substitution Method or Recursion Tree Method may be more suitable.
Conclusion
The Master Theorem is one of the most useful tools for analyzing divide-and-conquer algorithms.
Instead of expanding a recurrence repeatedly, we identify its parameters, compare the recursive contribution with the additional work, and apply the appropriate case.
With practice, many recurrence relations can be solved quickly.
In the next article, we will apply recurrence analysis to a classic problem: Tower of Hanoi Problem and Its Complexity Analysis.
Quick quiz
5 questionsOriginally published at farhanpaal.com — https://farhanpaal.com/articles/master-theorem-a-complete-guide/
Keep a copy
Read offline as a printout or PDF.
farhanpaal.com