Articles / DAA · Part 5

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.

Master Theorem: A Complete Guide

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 questions
In the recurrence \(T(n)=aT(n/b)+f(n)\), what does \(a\) represent?
What function do we compare \(f(n)\) against in the Master Theorem?
Which case applies to \(T(n)=2T(n/2)+1\)?
What is the complexity of Merge Sort using the Master Theorem?
When does Case 3 apply?

Keep a copy

Read offline as a printout or PDF.

farhanpaal.com

Keep reading

DAA · Part 1

What is DESIGN AND ANALYSIS OF ALGORITHM?

What is Design and Analysis of Algorithms (DAA)? Explore how algorithms are designed, analyzed for efficiency and correctness, and what this DAA…

6 min read

Ask Farhan

Ask anything about Farhan