Master Theorem Guide

The Setup

Form: $T(n) = aT(n/b) + f(n)$

• a ≥ 1 = number of recursive subproblems
• b > 1 = factor by which problem size shrinks
• f(n) = work done outside recursive calls (divide + combine)

Key Insight: Compare f(n) with n^(log_b a) to determine which dominates

Essential Logarithm Rules

$\log_b(b^x) = x \quad \text{Example: } \log_2(2^3) = 3$

$\log_b(a) = \frac{\log(a)}{\log(b)} \quad \text{Example: } \log_2(4) = \frac{\log(4)}{\log(2)} = 2$

$\log_b(xy) = \log_b(x) + \log_b(y) \quad \text{Example: } \log_2(8 \cdot 4) = \log_2(8) + \log_2(4) = 3 + 2 = 5$

$\log_b(x^k) = k \cdot \log_b(x) \quad \text{Example: } \log_2(n^3) = 3 \cdot \log_2(n)$

Most Critical: n^(log_b a) represents the "breakeven point"

The Three Cases

Case 1: Recursion Dominates

When: $f(n) = O(n^{\log_b a - \varepsilon})$ for some $\varepsilon > 0$ Result: $T(n) = \Theta(n^{\log_b a})$

Memory Trick: "Recursion wins" → Answer is just $n^{\log_b a}$

Case 2: Perfect Balance

When: $f(n) = \Theta(n^{\log_b a} \cdot \log^k n)$ for some $k \geq 0$ Result: $T(n) = \Theta(n^{\log_b a} \cdot \log^{k+1} n)$

Memory Trick: "Tied game" → Answer gets an extra log factor

Case 3: Outside Work Dominates

When: $f(n) = \Omega(n^{\log_b a + \varepsilon})$ AND regularity condition holds Result: $T(n) = \Theta(f(n))$

Memory Trick: "Outside work wins" → Answer is just $f(n)$

Regularity Condition: $a \cdot f(n/b) \leq c \cdot f(n)$ for some $c < 1$

Step-by-Step Process

Step 0: Preprocessing - Combine Identical Terms

CRITICAL: Before applying Master Theorem, check if you can combine identical recursive terms:

$T(n) = T(n/3) + T(n/3) + n = 2T(n/3) + n \quad \checkmark \text{ Can combine}$

$T(n) = T(n/2) + T(n/3) + n \quad \text{Cannot combine - different sizes} \quad \times$

Step 1: Identify Components

• Extract $a$, $b$, and $f(n)$ from $T(n) = aT(n/b) + f(n)$

Step 2: Calculate Critical Exponent

• Compute $c = \log_b a$
• This gives you $n^c = n^{\log_b a}$

Step 3: Compare and Classify

• Compare $f(n)$ with $n^c$
• Determine which case applies

Step 4: Apply Formula

• Use the corresponding case formula

Common Examples

Worked Examples

Example 1: Merge Sort

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

1. Identify: $a = 2$, $b = 2$, $f(n) = n$
2. Calculate: $\log_b a = \log_2 2 = 1$, so $n^{\log_b a} = n^1 = n$
3. Compare: $f(n) = n = \Theta(n^1 \log^0 n)$
4. Case: Case 2 with $k = 0$
5. Solution: $T(n) = \Theta(n^1 \log^{0+1} n) = \Theta(n \log n)$

Example 2: Binary Search

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

1. Identify: $a = 1$, $b = 2$, $f(n) = 1$
2. Calculate: $\log_b a = \log_2 1 = 0$, so $n^{\log_b a} = n^0 = 1$
3. Compare: $f(n) = 1 = \Theta(1 \cdot \log^0 n)$
4. Case: Case 2 with $k = 0$
5. Solution: $T(n) = \Theta(1 \cdot \log^{0+1} n) = \Theta(\log n)$

Example 3: Matrix Multiplication (Strassen)

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

1. Identify: $a = 7$, $b = 2$, $f(n) = n^2$
2. Calculate: $\log_b a = \log_2 7 \approx 2.807$, so $n^{\log_b a} = n^{2.807}$
3. Compare: $f(n) = n^2 = O(n^{2.807 - \varepsilon})$ for $\varepsilon = 0.8$
4. Case: Case 1
5. Solution: $T(n) = \Theta(n^{\log_2 7}) = \Theta(n^{2.807})$

Common Mistakes

Wrong: Forgetting to combine identical terms

T(n) = T(n/2) + T(n/2) + n
→ "This doesn't fit Master Theorem form"

Correct: $T(n) = 2T(n/2) + n$ → Apply Master Theorem

Wrong: Misidentifying f(n)

T(n) = 2T(n/2) + 3n + 5
→ f(n) = 3n (ignoring the constant)

Correct: $f(n) = 3n + 5 = \Theta(n)$

Wrong: Incorrect logarithm calculation

T(n) = 4T(n/2) + n
→ log₂(4) = 4

Correct: $\log_2(4) = 2$

Quick Reference Card

When you see: $T(n) = aT(n/b) + f(n)$

1. Calculate: $c = \log_b a$
2. Compare $f(n)$ with $n^c$:
   • If $f(n) < n^c$ → Case 1 → $\Theta(n^c)$
   • If $f(n) = n^c \log^k n$ → Case 2 → $\Theta(n^c \log^{k+1} n)$
   • If $f(n) > n^c$ → Case 3 → $\Theta(f(n))$

Most Common Results:

• Binary Search: $\Theta(\log n)$
• Merge Sort: $\Theta(n \log n)$
• Matrix Multiplication: $\Theta(n^3)$ (naive) or $\Theta(n^{2.807})$ (Strassen)