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:

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

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

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

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

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.