The Master Theorem for Solving Recurrence Relations

What Is the Master Theorem?

The Master Theorem provides a direct formula for solving recurrence relations of the form:

$$T(n) = aT!\left(\frac{n}{b}\right) + O!\left(n^c\right)$$

Where:
- $a \geq 1$: number of recursive sub-calls
- $b > 1$: factor by which input is divided
- $c \geq 0$: exponent in the non-recursive work $f(n) = O(n^c)$
- Base case: $T(1) = O(1)$

KEY TAKEAWAY: The Master Theorem compares the cost of recursive work ($n^{\log_b a}$) against the cost of non-recursive work ($n^c$). Whichever dominates determines the overall complexity.

The Three Cases

Let $\log_b a$ be the “critical exponent.” Compare $c$ to $\log_b a$:

Worked Examples

Example 1: Mergesort

$T(n) = 2T(n/2) + O(n)$

• $a = 2$, $b = 2$, $c = 1$
• $\log_b a = \log_2 2 = 1$
• $c = 1 = \log_b a$ → Case 2

$$T(n) = O(n^1 \log n) = O(n \log n)$$

Example 2: Binary Search

$T(n) = T(n/2) + O(1)$

• $a = 1$, $b = 2$, $c = 0$
• $\log_b a = \log_2 1 = 0$
• $c = 0 = \log_b a$ → Case 2

$$T(n) = O(n^0 \log n) = O(\log n)$$

Example 3: One sub-call, linear work

$T(n) = T(n/2) + O(n)$

• $a = 1$, $b = 2$, $c = 1$
• $\log_b a = 0$
• $c = 1 > 0 = \log_b a$ → Case 3

$$T(n) = O(n^1) = O(n)$$

Example 4: Eight sub-calls

$T(n) = 8T(n/2) + O(n^2)$

• $a = 8$, $b = 2$, $c = 2$
• $\log_b a = \log_2 8 = 3$
• $c = 2 < 3 = \log_b a$ → Case 1

$$T(n) = O(n^3)$$

Intuition Behind the Cases

• Case 1 ($c < \log_b a$): The recursion creates many sub-calls that together dominate the total work. Think of a tree with very many leaves.
• Case 2 ($c = \log_b a$): Work is evenly spread across all $\log n$ levels. Each level contributes equally.
• Case 3 ($c > \log_b a$): The top-level non-recursive work dominates; recursive work becomes negligible.

When Master Theorem Does NOT Apply

The Master Theorem applies only to recurrences of the form $T(n) = aT(n/b) + O(n^c)$.

It does not apply when:
- Sub-calls have different sizes (e.g., $T(n) = T(n/3) + T(2n/3) + O(n)$)
- The non-recursive term is not a polynomial (e.g., $O(n \log n)$)
- $a < 1$ or $b \leq 1$

EXAM TIP: VCAA exams always use the stated form. Identify $a$, $b$, and $c$; compute $\log_b a$; compare with $c$ to determine the case. Show these steps explicitly in your answer.