The master theorem

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Leaves in the recursion tree of a·T(n/b) + f(n)? from Lesson 1.2.2
• T(1) = 1, T(n) = 2T(n/2) + n: T(16)? from Lesson 1.2.1
• Is n log n = O(n^1.1)? from Lesson 1.1.2

1 · The Hook

🎣

The recursion tree always works, but drawing it costs minutes. The master theorem turns the three tree shapes into one comparison: f(n) against n^(log_b a). Most GATE recurrences are solved in under 30 seconds with it.

2 · Predict First

🤔

T(n) = 7T(n/2) + n². Compare n² with n^(log₂ 7) ≈ n^2.81. Which is bigger, and what does that say about the tree?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

n^2.81 is polynomially bigger than n², so the tree is bottom-heavy: T(n) = Θ(n^(log 7)) ≈ Θ(n^2.81) (Strassen's algorithm, Lesson 4.1.2).

The theorem

For T(n) = a·T(n/b) + f(n) with a ≥ 1, b > 1, let w = n^(log_b a) (the "watershed", the leaf count).

• f(n) = O(n^(log_b a − ε)) for some ε > 0 (f polynomially smaller than w): T(n) = Θ(n^(log_b a)).
• f(n) = Θ(n^(log_b a) · logᵏ n) with k ≥ 0 (f equals w up to logs): T(n) = Θ(n^(log_b a) · logᵏ⁺¹ n).
• f(n) = Ω(n^(log_b a + ε)) for some ε > 0 (f polynomially bigger) and a·f(n/b) ≤ c·f(n) for some c < 1 (regularity; true for polynomials): T(n) = Θ(f(n)).

Quick table (f(n) = nᵈ)

Compare a with bᵈ:

• a < bᵈ → Θ(nᵈ)
• a = bᵈ → Θ(nᵈ log n)
• a > bᵈ → Θ(n^(log_b a))

Worked list

When it does not apply

• a < 1, or b ≤ 1, or the subproblems are not of size n/b (T(n − 1)).
• f between cases by less than a polynomial factor in the "wrong" direction, e.g. T(n) = 2T(n/2) + n / log n: f = w·log⁻¹ n (k = −1) is not covered by case 2 as stated. (The extended rule gives Θ(n log log n).)
• Non-constant a (T(n) = n·T(n/2) + …).

4 · Visual

compare  f(n)  with  w = n^(log_b a)

   f << w (by n^eps)     f ~ w * log^k n        f >> w (by n^eps) + regularity
        |                      |                         |
   T = Theta(w)          T = Theta(w log^(k+1) n)    T = Theta(f)
   (leaves win)          (all levels equal)          (root wins)

5 · Worked Examples

Example 1 Easy

T(n) = 16T(n/4) + n. Solve.

Solution

w = n^(log₄ 16) = n²; f = n is smaller → Θ(n²).

Example 2 Medium

T(n) = 8T(n/2) + n³. Solve.

Solution

w = n³ = f → case 2 → Θ(n³ log n).

Example 3 GATE

T(n) = 2T(n/2) + n/log n. Does the basic master theorem apply?

Solution

No: f = n/log n is smaller than w = n, but only by a log factor, not by n^ε, and case 2 needs k ≥ 0. (Extended form: Θ(n log log n).)

6 · GATE Traps

⚠️

• Compare with n^(log_b a), not with n.
• "Polynomially smaller/bigger" means by a factor n^ε; a log factor is not enough for cases 1 and 3.
• Case 2 with logᵏ adds one more log.
• T(n − 1)-type recurrences are not master-theorem recurrences.

7 · Memory Hook

🧠

"a versus bᵈ: less → nᵈ, equal → nᵈ log n, more → n^(log_b a)."

8 · Connect the Dots

The master theorem handles a·T(n/b) + f(n). Next: the recurrences it cannot touch, square roots, T(n − 1) chains and uneven splits.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markMaster case

T(n) = 4T(n/2) + n³ is:

• (A) Θ(n³ log n)
• (B) Θ(n²)
• (C) Θ(n² log n)
• (D) Θ(n³)

Q2NAT1 markExponent

T(n) = 25T(n/5) + n. T(n) = Θ(nᵏ). k = ?

Numerical answer: ________

Q3MCQ1 markCase 2 with logs

T(n) = 2T(n/2) + n log n is:

• (A) Θ(n log n)
• (B) Θ(n log² n)
• (C) Θ(n²)
• (D) Θ(n log log n)

Q4MCQ1 markSquare root

T(n) = 2T(n/4) + √n is:

• (A) Θ(√n log n)
• (B) Θ(n)
• (C) Θ(log n)
• (D) Θ(√n)

Q5MSQ2 marksApplicability

For which recurrences does the basic master theorem apply directly?

• (A) T(n) = 3T(n/3) + n
• (B) T(n) = T(n − 1) + n
• (C) T(n) = 2T(n/2) + n/log n
• (D) T(n) = 5T(n/2) + n²

10 · Rule Card

• T(n) = aT(n/b) + f(n); w = n^(log_b a).
• f = O(w/n^ε) → Θ(w); f = Θ(w logᵏ n), k ≥ 0 → Θ(w logᵏ⁺¹ n); f = Ω(w·n^ε) + regularity → Θ(f).
• f = nᵈ: compare a with bᵈ.
• Not for T(n−1), a < 1, gaps (n/log n), non-constant a.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

master theoremwatershed n^(log_b a)case 1, case 2 (with logᵏ), case 3regularity conditionpolynomially smaller/largergaps of the master theorem

12 · Answer Vault