Master Theorem for Recurrences

Learning Objectives

By the end of this section, you will be able to:

1. Understand what recurrence relations are and how they arise in divide-and-conquer algorithms
2. Apply the Master Theorem to solve recurrences of the form $T(n) = aT(n/b) + f(n)$
3. Identify which of the three cases applies by comparing $f(n)$ to $n^{\log_b a}$
4. Visualize recurrence trees to build intuition about where work is done
5. Analyze famous algorithms like merge sort, binary search, and Strassen's algorithm
6. Recognize when the Master Theorem does not apply

Why This Matters: The Master Theorem is one of the most powerful tools in algorithm analysis. It allows you to immediately determine the complexity of any divide-and-conquer algorithm without tedious mathematical derivations. This is essential for technical interviews and for making informed algorithm design decisions.

The Story: Divide and Conquer

Many of the most elegant and efficient algorithms follow a pattern called divide and conquer:

1. Divide: Break the problem into smaller subproblems
2. Conquer: Solve the subproblems recursively
3. Combine: Merge the subproblem solutions into a solution for the original problem

Consider sorting an array of n elements. The naive approach compares all pairs, taking $O(n^2)$ time. But merge sort divides the array in half, recursively sorts each half, then merges them:

This gives us a recurrence relation: $T(n) = 2T(n/2) + O(n)$. But what does this equal? Is it faster than $O(n^2)$?

The Master Theorem answers this question instantly: $T(n) = \Theta(n \log n)$. Much faster than the naive $O(n^2)$ approach!

Recurrence Relations

A recurrence relation expresses the running time of a recursive algorithm in terms of smaller inputs. For divide-and-conquer algorithms, recurrences have this general form:

Where:

• $a \geq 1$: Number of subproblems (recursive calls)
• $b > 1$: Factor by which problem size shrinks
• $f(n)$: Cost of dividing and combining (non-recursive work)

Examples of Recurrences

The key question: given $a$, $b$, and $f(n)$, what is the total running time $T(n)$?

The Master Theorem

The Master Theorem provides a "cookbook" solution for recurrences of the form above. The answer depends on how $f(n)$ compares to a critical value: $n^{\log_b a}$.

The Critical Value: $n^{\log_b a}$

The magic number $n^{\log_b a}$ represents the cost of all the leavesin the recursion tree. Why? Because:

• The tree has height $\log_b n$ (we divide by b each level until reaching base case)
• At each level, we multiply the number of problems by a
• Total leaves = $a^{\log_b n} = n^{\log_b a}$

The Master Theorem compares the work at the leaves ($n^{\log_b a}$) to the work at each level ($f(n)$) to determine which dominates.

Case 1: Recursion Dominates

When it applies: $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$

Intuition: The work at each level increases as we go down the tree. Most work is done at the leaves. The recursion overwhelms the combining work.

Result: $T(n) = \Theta(n^{\log_b a})$

Example: T(n) = 4T(n/2) + n

Let's analyze step by step:

1. Identify parameters: $a = 4$, $b = 2$, $f(n) = n$
2. Calculate critical value: $\log_2 4 = 2$, so $n^{\log_b a} = n^2$
3. Compare: $f(n) = n$ vs $n^2$. Since $n = O(n^{2-1}) = O(n^1)$, we have $f(n) = O(n^{\log_b a - \epsilon})$ with $\epsilon = 1$
4. Case 1 applies: $T(n) = \Theta(n^2)$

Why? We make 4 recursive calls on problems half the size. The branching factor (4) exceeds the shrinkage (2), so work explodes down the tree. The n work at each level is dwarfed by the n² leaves.

Case 2: Balanced Work

When it applies: $f(n) = \Theta(n^{\log_b a})$

Intuition: The work is equal at every level of the recursion tree. No level dominates; all contribute equally. Total work = (work per level) × (number of levels).

Result: $T(n) = \Theta(n^{\log_b a} \log n)$

Example: T(n) = 2T(n/2) + n (Merge Sort)

This is the most famous Case 2 example:

1. Parameters: $a = 2$, $b = 2$, $f(n) = n$
2. Critical value: $\log_2 2 = 1$, so $n^{\log_b a} = n^1 = n$
3. Compare: $f(n) = n = \Theta(n)$. They match exactly!
4. Case 2 applies: $T(n) = \Theta(n \log n)$

Why? At each level of the recursion tree, the total work is exactly n:

Each of the $\log n$ levels contributes n work, giving $\Theta(n \log n)$ total.

T(1) = O(1)

This contributes T(n/2) to the recurrence

Another T(n/2) contribution

This is the f(n) = n term in our recurrence

1def merge_sort(arr):
2    if len(arr) <= 1:
3        return arr
4
5    mid = len(arr) // 2
6    left = merge_sort(arr[:mid])
7    right = merge_sort(arr[mid:])
8
9    return merge(left, right)
10
11def merge(left, right):
12    result = []
13    i = j = 0
14    while i < len(left) and j < len(right):
15        if left[i] <= right[j]:
16            result.append(left[i])
17            i += 1
18        else:
19            result.append(right[j])
20            j += 1
21    result.extend(left[i:])
22    result.extend(right[j:])
23    return result

Case 3: Root Dominates

When it applies: $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$, and the regularity condition $af(n/b) \leq cf(n)$ holds for some $c < 1$

Intuition: The work decreases as we go down the tree. Most work is done at the root. The combining work overwhelms the recursion.

Result: $T(n) = \Theta(f(n))$

Example: T(n) = 2T(n/2) + n²

1. Parameters: $a = 2$, $b = 2$, $f(n) = n^2$
2. Critical value: $n^{\log_2 2} = n$
3. Compare: $f(n) = n^2 = \Omega(n^{1+1}) = \Omega(n^{\log_b a + \epsilon})$ with $\epsilon = 1$
4. Check regularity: $2 \cdot (n/2)^2 = n^2/2 \leq (1/2) \cdot n^2$. Yes, with c = 1/2.
5. Case 3 applies: $T(n) = \Theta(n^2)$

Why? The work at each level shrinks geometrically:

Total work = $n^2 + n^2/2 + n^2/4 + \cdots < 2n^2 = \Theta(n^2)$. The geometric series converges, and the root dominates.

Interactive: Master Theorem Explorer

Use this interactive tool to explore the Master Theorem. Adjust the parameters a, b, and f(n) to see which case applies and what the solution is.

The Recursion Tree Method

The Master Theorem is actually derived from analyzing recursion trees. Understanding this visualization gives deep intuition for why the three cases exist.

Structure of a Recursion Tree

• Root: The original problem of size n, doing f(n) work
• Each level: aⁱ nodes, each of size n/bⁱ
• Height: log_b n levels until we reach the base case
• Leaves: a^{log_b n} = n^{log_b a} base cases

The total work is the sum of work at all levels. Depending on whether work increases, stays constant, or decreases as we go down, we get Cases 1, 2, or 3.

Famous Algorithm Examples

Let's apply the Master Theorem to some of the most important algorithms in computer science.

Binary Search - O(log n)

Recurrence: $T(n) = T(n/2) + 1$

a = 1, b = 2, f(n) = 1

1def binary_search(arr, target, left=0, right=None):
2    if right is None:
3        right = len(arr) - 1
4
5    if left > right:
6        return -1
7
8    mid = (left + right) // 2
9
10    if arr[mid] == target:
11        return mid
12    elif arr[mid] < target:
13        return binary_search(arr, target, mid + 1, right)
14    else:
15        return binary_search(arr, target, left, mid - 1)

Analysis: a=1, b=2, f(n)=1. Since log₂(1)=0, we have n^{log_b a} = 1 = f(n).Case 2: T(n) = Θ(log n).

Merge Sort - O(n log n)

Recurrence: $T(n) = 2T(n/2) + n$

Analysis: a=2, b=2, f(n)=n. Since log₂(2)=1, we have n^{log_b a} = n = f(n).Case 2: T(n) = Θ(n log n).

Strassen's Matrix Multiplication - O(n^2.81)

Recurrence: $T(n) = 7T(n/2) + n^2$

log₂(7) ≈ 2.81 < 3 = log₂(8)

f(n) = n² work to combine

1def strassen(A, B):
2    n = len(A)
3    if n == 1:
4        return [[A[0][0] * B[0][0]]]
5
6    # Split matrices into quadrants
7    # ... (splitting code)
8
9    # 7 recursive multiplications (not 8!)
10    P1 = strassen(A11 + A22, B11 + B22)
11    P2 = strassen(A21 + A22, B11)
12    P3 = strassen(A11, B12 - B22)
13    P4 = strassen(A22, B21 - B11)
14    P5 = strassen(A11 + A12, B22)
15    P6 = strassen(A21 - A11, B11 + B12)
16    P7 = strassen(A12 - A22, B21 + B22)
17
18    # Combine results with O(n^2) additions
19    # C11 = P1 + P4 - P5 + P7
20    # ... (combination code)
21    return C

Analysis: a=7, b=2, f(n)=n². Since log₂(7)≈2.81, we have n^{log_b a} ≈ n^2.81. Since n² = O(n^2.81-0.81) = O(n²), Case 1 applies: T(n) = Θ(n^2.81).

This is better than the naive O(n³)! Strassen's key insight was reducing from 8 to 7 recursive multiplications, changing log₂(8)=3 to log₂(7)≈2.81.

Summary Table

When the Master Theorem Doesn't Apply

The Master Theorem is powerful but not universal. It fails in several situations:

1. Non-Polynomial Gaps

The theorem requires $f(n)$ to be polynomially smaller or larger than $n^{\log_b a}$. A logarithmic gap doesn't qualify:

Here n/log n is not O(n^1-ε) for any ε > 0, nor Θ(n), nor Ω(n^1+ε). The Master Theorem doesn't apply. (The answer is Θ(n log log n), found by other methods.)

2. Unequal Subproblem Sizes

The Master Theorem assumes all subproblems have the same size n/b. Consider:

This has two subproblems of different sizes (n/3 and 2n/3). The standard Master Theorem doesn't apply, though the Akra-Bazzi theorem can handle this case.

3. Variable Number of Subproblems

If the number of recursive calls depends on the input:

This doesn't fit the aT(n/b) + f(n) form because a = √n changes with n.

4. Non-Constant Base Case

If the base case isn't Θ(1), additional analysis may be needed.

Test Your Understanding

Put your knowledge to the test! Identify which case of the Master Theorem applies to each recurrence and determine the solution.

Summary

The Master Theorem provides a powerful shortcut for analyzing divide-and-conquer algorithms:

Key Concepts

Quick Reference

The 3-Second Test: Compare k (exponent of n in f(n)) to log_b(a):

• k < log_b(a) → Recursion dominates → Θ(n^{log_b a})
• k = log_b(a) → Balanced → Θ(n^k log n)
• k > log_b(a) → Root dominates → Θ(n^k)

Why This Matters

• Technical Interviews: You'll be asked to analyze recursive algorithms. The Master Theorem gives instant answers.
• Algorithm Design: Knowing how a and b affect complexity helps you design better divide-and-conquer algorithms.
• Optimization Insights: Strassen saved 0.19 in the exponent by reducing from 8 to 7 subproblems. Understanding this tradeoff is crucial.

Exercises

Basic Analysis

1. Apply the Master Theorem to: $T(n) = 9T(n/3) + n$
2. Apply the Master Theorem to: $T(n) = T(n/2) + n^2$
3. Apply the Master Theorem to: $T(n) = 4T(n/2) + n^2$
4. Apply the Master Theorem to: $T(n) = 2T(n/4) + \sqrt{n}$

Algorithm Analysis

1. An algorithm divides a problem of size n into 3 subproblems of size n/2, and spends O(n) time on dividing and combining. Write the recurrence and solve it.
2. If we could improve Strassen's algorithm to make only 6 recursive calls instead of 7, what would the new complexity be?
3. A recursive algorithm has recurrence T(n) = 8T(n/2) + n². What is its complexity? How does this compare to the naive cubic matrix multiplication?

Deeper Understanding

1. Explain why reducing from 8 to 7 subproblems in matrix multiplication (Strassen) provides such a significant improvement for large matrices.
2. For what values of k does the recurrence T(n) = 4T(n/2) + n^k satisfy Case 1? Case 2? Case 3?
3. Why doesn't the Master Theorem apply to T(n) = 2T(n/2) + n log n? What additional condition would be needed?

You've now mastered one of the most important tools in algorithm analysis. The Master Theorem transforms complex recurrence analysis into a simple comparison, enabling you to quickly assess the efficiency of any divide-and-conquer algorithm.

In the next chapter, we'll explore Mathematical Foundations that underpin algorithm analysis, including logarithms, summations, and proof techniques that complement the Master Theorem.