Master Theorem

CSS Computer Science (Optional) — Paper-I, Section-B, Topic IV. Companion page to Recurrence Relations (which introduces the Master Theorem as one of four solving methods). This page goes deep on just the Master Theorem: the formal statement, the recursion-tree intuition behind why it works, every case worked through multiple examples, the generalized/extended version, the gap case where it fails, and the exam traps FPSC likes to set.

What the Master Theorem Is For

• A shortcut that gives the closed-form solution of any recurrence of the exact shape $T(n) = a\cdot T(n/b) + f(n)$ directly — without expanding it step by step (Substitution) or drawing it out level by level (Recursion Tree).
• Conditions for it to apply: $a \geq 1$ (number of subproblems per call), $b > 1$ (factor each subproblem shrinks by), and $f(n)$ asymptotically positive (the non-recursive work done at each call — dividing/combining).
• It only handles equal-sized subproblems with constant a and b. Anything else (unequal splits, a or b depending on n, purely subtractive recurrences like T(n-1)) is out of scope — use Substitution or a Recursion Tree instead.

Exam angle: the very first thing to check, before touching the theorem at all, is whether the recurrence is actually in this shape. FPSC sets recurrences that look similar but aren't (see "When It Doesn't Apply" below) specifically to test this recognition step.

---

Recursion-Tree Intuition — Why the Theorem Works

Picture the call tree of $T(n) = a\cdot T(n/b) + f(n)$:

• At depth i, there are $a^i$ subproblems, each of size $n/b^i$.
• The tree bottoms out (reaches the base case, size 1) at depth $i = \log_b n$.
• Total number of leaves = $a^{\log_b n} = n^{\log_b a}$ — this quantity, often called the "watershed function," is the amount of work the pure branching structure alone would cost if every call did O(1) work.
• The actual total work is a race between two things: $n^{\log_b a}$ (cost concentrated at the leaves, i.e. how much the recursion itself costs) versus $f(n)$ summed across levels (cost concentrated at the top, i.e. how much the non-recursive divide/combine step costs).

This is exactly what the three cases compare — whichever side of that race wins, dominates the total, and that's the answer:

Key reasoning point: this is the single most useful way to remember the three cases without memorizing them by rote — you're always just asking "does the branching win, tie, or lose against the combine-step cost?"

---

Formal Statement

Given $T(n) = a\cdot T(n/b) + f(n)$ with $a \geq 1$, $b > 1$, let $n^{\log_b a}$ be the watershed function. Compare $f(n)$ to it:

Why the ε ("polynomially") matters: it's not enough for f(n) to be merely asymptotically smaller or larger than the watershed function — it must be smaller/larger by at least a factor of $n^\varepsilon$ for some fixed ε. This is precisely what excludes the gap case below (like $f(n) = n/\log n$, which is smaller than n but not by any polynomial factor).

Why the regularity condition (Case 3) matters: it's a technical requirement ensuring the total non-recursive cost really is dominated by the root's f(n) rather than blowing up somewhere in the middle of the tree. In practice, almost every polynomial or polynomial-times-log f(n) you'll meet in an exam satisfies it automatically — but you must still state that you checked it, because FPSC marks it as a separate step.

---

Case 1 — Worked Examples (branching dominates)

Example 1: T(n) = 9T(n/3) + n

$a=9, b=3, f(n)=n$. Watershed: $n^{\log_3 9} = n^2$. Compare: $f(n)=n=O(n^{2-\varepsilon})$ with $\varepsilon=1$ → Case 1.

$$T(n) = \Theta(n^2)$$

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

$a=8, b=2, f(n)=n^2$. Watershed: $n^{\log_2 8} = n^3$. Compare: $f(n)=n^2=O(n^{3-\varepsilon})$ with $\varepsilon=1$ → Case 1.

$$T(n) = \Theta(n^3)$$

---

Case 2 — Worked Examples (tied at every level)

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

$a=2, b=2, f(n)=cn$. Watershed: $n^{\log_2 2} = n^1 = n$. Compare: $f(n)=\Theta(n)$ → exact match → Case 2.

$$T(n) = \Theta(n \log n)$$

— confirms the recursion-tree derivation on the Recurrence Relations page.

Example 2: Binary Search — T(n) = T(n/2) + c

$a=1, b=2, f(n)=c$. Watershed: $n^{\log_2 1} = n^0 = 1$. Compare: $f(n)=\Theta(1)$ → exact match → Case 2.

$$T(n) = \Theta(\log n)$$

Extended (Generalized) Case 2 — with an extra log factor

If $f(n) = \Theta(n^{\log_b a} \cdot \log^k n)$ for some constant $k \geq 0$, the generalized theorem gives:

$$T(n) = \Theta\big(n^{\log_b a} \cdot \log^{k+1} n\big)$$

Example: $T(n) = 2T(n/2) + n\log n$. Here $a=2,b=2$, watershed $=n$, and $f(n)=n\log n = n^1 \cdot \log^1 n$ matches the pattern with k=1.

$$T(n) = \Theta(n \log^2 n)$$

Exam angle: this generalized version is a favorite "advanced" twist on an otherwise standard Case-2 question — recognize $n\log n$ (not plain n) as the trigger for the extra +1 power of log.

---

Case 3 — Worked Example (combine step dominates)

T(n) = 3T(n/4) + n log n

$a=3, b=4, f(n)=n\log n$. Watershed: $n^{\log_4 3} \approx n^{0.79}$. Compare: $f(n)=n\log n = \Omega(n^{0.79+\varepsilon})$ — grows polynomially faster → candidate for Case 3.

Check the regularity condition:

$$a\cdot f(n/b) = 3\cdot\frac{n}{4}\log\frac{n}{4} \leq \frac{3}{4}\cdot n\log n = c\cdot f(n)$$

with $c = 3/4 < 1$ → holds.

$$T(n) = \Theta(n \log n)$$

Exam angle: always show the regularity-condition check explicitly for a Case-3 answer — stating "f(n) grows faster, so Case 3" without checking regularity is an incomplete answer even if the final Big-O happens to be right.

---

When the Master Theorem Does NOT Apply (the "gap" case)

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

$a=2, b=2, f(n)=n/\log n$. Watershed: $n^{\log_2 2} = n$.

• Case 1 test: is $n/\log n = O(n^{1-\varepsilon})$? No — $n/\log n$ is not polynomially smaller than n (dividing by log n is weaker than dividing by any $n^\varepsilon$).
• Case 2 test: is $n/\log n = \Theta(n)$? No — it's smaller by a log factor, not equal.
• Case 3 test: is $n/\log n = \Omega(n^{1+\varepsilon})$? No — it's smaller than n, not larger.

None of the three cases fit — the Master Theorem is inapplicable. (The actual answer, obtainable via the more general Akra–Bazzi method or a careful recursion-tree sum, is $T(n) = \Theta(n\log\log n)$, but deriving that is beyond what FPSC expects — the tested skill is recognizing the gap and stating the theorem doesn't apply.)

Other common "doesn't apply" shapes

---

Domain-Transformation Example — Making the Master Theorem Apply

Some recurrences aren't in the aT(n/b)+f(n) shape as written, but a substitution turns them into one — after which the Master Theorem applies normally. The classic trigger is a T(√n) term.

T(n) = T(√n) + log n (n ≥ 2), T(n) = O(1) otherwise

Step 1 — recognize it doesn't fit directly: the recursive call is T(√n), not T(n/b) for constant b, so the Master Theorem can't be applied as-is.

Step 2 — substitute n = 2^m (i.e. m = log₂n), and define S(m) = T(2^m):

• √n = 2^(m/2), so T(√n) = T(2^(m/2)) = S(m/2)
• log n = log(2^m) = m
• The recurrence becomes: S(m) = S(m/2) + m — now in standard Master Theorem shape.

Step 3 — apply the Master Theorem to S(m): a=1, b=2, f(m)=m. Watershed: m^log₂(1) = m⁰ = 1. Compare: f(m)=m=Ω(m^(0+ε)) with ε=1 → candidate Case 3.

Check regularity: a·f(m/b) = 1·(m/2) = m/2 ≤ (1/2)·m = c·f(m) with c=1/2 \< 1 → holds.

→ S(m) = Θ(f(m)) = Θ(m)

Step 4 — substitute back m = log n:

T(n) = Θ(log n)

Exam angle: this is the favorite way FPSC dresses up a Case-3 question as something that "can't" use the Master Theorem — the fix is always the same substitution n=2^m (equivalently m=log n), which turns any T(√n) into T(m/2).

---

Decision Flowchart

1. Is it shaped $T(n) = a\cdot T(n/b) + f(n)$ with constant $a \geq 1$, constant $b > 1$? If no — Master Theorem doesn't apply; use Substitution or Recursion Tree.
2. Compute the watershed function $n^{\log_b a}$.
3. Compare f(n) against it:
   • Polynomially smaller (by $n^\varepsilon$) → Case 1 → $\Theta(n^{\log_b a})$
   • Same order, optionally times $\log^k n$ → Case 2 / generalized → $\Theta(n^{\log_b a}\cdot\log^{k+1} n)$
   • Polynomially larger (by $n^\varepsilon$) and regularity holds → Case 3 → $\Theta(f(n))$
   • None of the above (a "gap," e.g. differs by only a log factor) → Master Theorem does not apply

---

Master Theorem vs the Other Methods — When to Reach for Which

Full coverage of the other three methods, with worked examples, is on the Recurrence Relations page.

---

📌 Frequently Tested Pattern — Master Theorem (CSS/FPSC)

Master Theorem questions on CS papers tend to take one of three forms: (1) a direct "solve T(n) = ... using the Master Theorem" with a clean Case-1/2/3 recurrence, (2) a "which case applies" classification MCQ, or (3) a conceptual "why can't you use the Master Theorem here" question using one of the out-of-scope shapes above. These practice items are modeled on that pattern (not sourced from a specific verified past paper — drill them alongside the one verified past recurrence question, the 2016 Binary Search substitution problem, documented on the Recurrence Relations page):

1. Direct application: Solve $T(n) = 4T(n/2) + n$ using the Master Theorem. ($a=4,b=2$ → watershed $n^2$; $f(n)=n=O(n^{2-\varepsilon})$ → Case 1 → $\Theta(n^2)$.)
2. Classification MCQ: For $T(n) = T(n/2) + n$, which Master Theorem case applies? A) Case 1 B) Case 2 C) Case 3 D) None apply. ($a=1,b=2$ → watershed $n^0=1$; $f(n)=n=\Omega(n^{0+\varepsilon})$ and regularity $1\cdot f(n/2)=n/2\leq c\cdot n$ holds for $c=1/2$ → Case 3 → $\Theta(n)$. Correct answer: C, not A — a common trap is assuming a small a always means Case 1.)
3. Conceptual (why it fails): Explain why the Master Theorem cannot classify $T(n) = 2T(n/2) + n/\log n$. (See the gap-case section above — f(n) is neither polynomially smaller, equal to, nor polynomially larger than the watershed $n^1$.)
4. Generalized case: Solve $T(n) = 4T(n/2) + n^2\log n$ using the Master Theorem. ($a=4,b=2$ → watershed $n^2$; $f(n)=n^2\log n$ matches $n^{\log_b a}\cdot\log^1 n$ → generalized Case 2 with k=1 → $\Theta(n^2\log^2 n)$.)
5. Regularity check: For $T(n) = 3T(n/4) + n\log n$, state which case applies and explicitly verify the regularity condition. (Case 3 — full check worked above.)

Exam angle — the highest-leverage habit: always write out $a = \ldots$, $b = \ldots$, $f(n) = \ldots$, and the watershed $n^{\log_b a} = \ldots$ as explicit labeled lines before stating a case. FPSC awards marks for this setup separately from the final Θ() answer, and it's also what prevents the Example-2 classification trap above.