Master theorem — solving recurrences T(n) = aT(n - b) + f(n): Worked examples

This page is a shooting range. The parent note on T(n) = aT(n / b) + f(n) gave you the three cases. Here we fire a bullet at every target: each case, the tricky ties, the degenerate inputs ( $a = 1$ , $f$ constant), the log-gap trap that lives between the cases, a real-world word problem, and an exam-style twist that looks like one case but is another.

Before any example, three reminders in plain words so nothing is used before it is built.

Look at the picture below: the same recursion tree drawn three ways. The red shape is whichever pile wins. That single picture is the whole theorem.

Figure — Master theorem — solving recurrences T(n) = aT(n - b) + f(n)

Figure s01 — a horizontal bar chart shown in three side-by-side panels; each panel stacks five bars, one per tree level, with the root at the top and the leaf row at the bottom, and the bar length is the total work done on that level. Left panel (Case 1, leaves win): bars grow longer as you go down, and the longest bar — the bottom leaf row — is drawn in red, so the leaf pile dominates. Middle panel (Case 2, tie): all five bars are the same length and each is outlined in red, showing every floor costs the same, so you pay per floor ( $\times lo g n$ ). Right panel (Case 3, root wins): bars shrink as you go down, and the longest bar — the top root row — is drawn in red, so the root/combine pile dominates. A red arrow in each panel points at the winning bar with a short label ("leaf pile biggest" / "all floors equal" / "root pile biggest").

The scenario matrix

Every recurrence the basic theorem can eat falls into exactly one of these cells. The examples that follow are each tagged with the cell they hit, so you can see the whole board is covered.

Cell	What makes it this cell	Answer shape	Example #
A — Case 1, leaves win	$f$ polynomially smaller than $n^{l o g_{b} a}$	$Θ (n^{l o g_{b} a})$	1
A′ — Case 1, degenerate $f = Θ (1)$	constant combine, $a > 1$	$Θ (n^{l o g_{b} a})$	2
B — Case 2, plain tie	$f = Θ (n^{l o g_{b} a})$ , no extra log	$Θ (n^{l o g_{b} a} lo g n)$	3
C — Case 2, degenerate $a = 1$	tree is a single stick, $n^{l o g_{b} a} = n^{0} = 1$	$Θ (lo g n)$	4
D — Case 3, root wins	$f$ polynomially bigger + regularity holds	$Θ (f (n))$	5
E — Case 3 regularity fails	$f$ bigger but $a f (n / b) \neq \leq c f (n)$	theorem refuses; must fall back	6
F — the log-gap trap	$f$ bigger only by a log, not a polynomial	extended Case 2, $Θ (n^{l o g_{b} a} lo g^{k + 1} n)$	7
G — real-world word problem	translate prose → $a, b, f$ first	whichever case results	8
H — exam twist (looks like X, is Y)	disguised leaf cost / hidden $lo g$	trap-aware answer	9

The "signs/quadrants" of this topic are which pile wins (leaves / tie / root); the degenerate inputs are $a = 1$ (single stick, cell C) and $f = Θ (1)$ (constant combine, cell A′). We hit them all.

The worked examples

Worked example

Example 1 — Cell A (leaves win) · $T (n) = 8 T (n /2) + n^{2}$ Forecast: eight subproblems is a lot — guess the leaves swamp the tiny $n^{2}$ combine. Guess $n^{3}$ -ish. Write your guess down before reading on.

Read off constants. $a = 8, b = 2, f (n) = n^{2}$ . Why this step? The theorem only sees $a, b, f$ ; everything starts by naming them.
Compute the leaf exponent. $lo g_{b} a = lo g_{2} 8 = 3$ , so leaf cost $= n^{3}$ . Why this step? $n^{l o g_{b} a}$ is the ruler we compare $f$ against — nothing else matters until we have it.
Compare $f$ to the ruler. $f (n) = n^{2}$ versus $n^{3}$ . Since $n^{2} = O (n^{3 - ϵ})$ (take $ϵ = 1$ ), $f$ is polynomially smaller. Why this step? "Polynomially smaller" = smaller by a genuine power of $n$ , which is exactly the trigger for Case 1 (leaves dominate).
Apply Case 1. $T (n) = Θ (n^{l o g_{b} a}) = Θ (n^{3})$ .

Verify: count the leaves directly — $8^{l o g_{2} n} = n^{l o g_{2} 8} = n^{3}$ . The bottom row alone already costs $n^{3}$ , so the answer can't be smaller. Guess confirmed. ✓

Worked example

Example 2 — Cell A′ (degenerate constant combine) · $T (n) = 2 T (n /2) + 1$ Forecast: two subproblems each level, but the combine is a mere constant. Does constant $f$ mean the answer is constant? Or do the leaves take over? Guess first — this is the counterpart to Binary Search but with branching.

Read off constants. $a = 2, b = 2, f (n) = 1 = Θ (1)$ . Why this step? Naming $a, b, f$ is always first; here $f$ is a constant, the degenerate combine we promised to cover.
Compute the leaf exponent. $lo g_{2} 2 = 1$ , so leaf cost $= n^{1} = n$ . Why this step? We must build the ruler before we can see whether the constant $f$ sits below or on it.
Compare $f$ to the ruler. $f (n) = 1$ versus $n$ . A constant is $O (n^{1 - ϵ})$ (take $ϵ = 1$ , then $n^{0} = 1$ — still $O$ of the same order, and any $ϵ < 1$ gives strict polynomial smallness). So $f$ is polynomially smaller → Case 1. Why this step? This is the key lesson of the cell: a constant $f$ almost always loses to a branching tree, because $a > 1$ makes the leaf count grow like a real power of $n$ while $f$ stays flat.
Apply Case 1. $T (n) = Θ (n^{l o g_{b} a}) = Θ (n)$ .

Verify: count nodes in the whole tree — a full binary tree with $n$ leaves has about $2 n - 1$ nodes, each doing $O (1)$ work, so total $= Θ (n)$ . Constant combine, linear answer — the leaves ran the show. ✓

Worked example

Example 3 — Cell B (plain tie) · Merge-style · $T (n) = 4 T (n /2) + n^{2}$ Forecast: four subproblems, each half-size, combine cost $n^{2}$ . Does the $n^{2}$ combine tie the leaves? Guess first.

Read off constants. $a = 4, b = 2, f (n) = n^{2}$ . Why this step? The theorem sees only $a, b, f$ ; we must name them before any comparison is possible.
Compute the leaf exponent. $lo g_{2} 4 = 2$ , so leaf cost $= n^{2}$ . Why this step? We build the ruler $n^{l o g_{b} a}$ first because Case 2 is defined by $f$ matching this ruler — we can't spot a tie without it.
Compare. $f (n) = n^{2} = Θ (n^{2}) = Θ (n^{l o g_{b} a} lo g^{0} n)$ . Exact match with $k = 0$ . Why this step? When $f$ equals the ruler ( $Θ$ , not $O$ or $Ω$ ), no pile wins; every level of the tree costs the same, so we're in Case 2.
Apply Case 2. $T (n) = Θ (n^{2} lo g^{0 + 1} n) = Θ (n^{2} lo g n)$ . Why the $lo g$ ? Look at figure s01, middle panel: each floor is the same length, and there are $lo g_{2} n$ floors, so total $=$ (per-floor cost) $\times$ (number of floors).

Verify: at $n = 16$ , floors $= lo g_{2} 16 = 4$ , each floor $\approx 1 6^{2} = 256$ , total $\approx 4 \times 256 = 1024$ . And $n^{2} lo g_{2} n = 256 \times 4 = 1024$ . Matches. ✓

Worked example

Example 4 — Cell C (degenerate $a = 1$ ) · Binary Search · $T (n) = T (n /2) + 1$ Forecast: you throw away half the array and do $O (1)$ work. Guess $lo g n$ . This is Binary Search.

Read off constants. $a = 1, b = 2, f (n) = 1$ . Why this step? Naming $a, b, f$ is the fixed opening move; note $a = 1$ , the single-stick degenerate input.
Compute the leaf exponent. $lo g_{2} 1 = 0$ , so leaf cost $= n^{0} = 1$ . Why this step? $a = 1$ means the tree is a single stick — one node per level, not a branching tree — and $n^{0} = 1$ says the leaf count is literally $1$ . We need this ruler to see it's a tie, not a win.
Compare. $f (n) = 1 = Θ (n^{0} lo g^{0} n)$ . A tie at the constant level, $k = 0$ . Why this step? Both piles are constant ( $Θ$ of each other), so neither dominates → Case 2.
Apply Case 2. $T (n) = Θ (n^{0} lo g^{0 + 1} n) = Θ (lo g n)$ .

Verify: unroll by hand — $T (n) = 1 + 1 + \dots + 1$ once per halving, and you can halve $n$ down to $1$ exactly $lo g_{2} n$ times. Sum $= lo g_{2} n = Θ (lo g n)$ . ✓

Worked example

Example 5 — Cell D (root wins, regularity holds) · $T (n) = 2 T (n /2) + n^{2}$ Forecast: only two subproblems but an expensive $n^{2}$ combine. The combine should swamp the leaves. Guess $n^{2}$ .

Read off constants. $a = 2, b = 2, f (n) = n^{2}$ . Why this step? Fixed opening move — the theorem only reads $a, b, f$ .
Compute the leaf exponent. $lo g_{2} 2 = 1$ , leaf cost $= n^{1}$ . Why this step? We need the ruler to see that $f = n^{2}$ sits above it — the trigger for Case 3.
Compare. $f (n) = n^{2} = Ω (n^{1 + ϵ})$ with $ϵ = 1$ — polynomially bigger. Why this step? Bigger-by-a-real-power ( $Ω$ with a genuine exponent gap) is the trigger for "root wins", but Case 3 is the only case with a second door — regularity.
Regularity check. $a f (n / b) = 2 (\frac{n}{2})^{2} = \frac{n ^{2}}{2} = \frac{1}{2} f (n) \leq c f (n)$ with $c = \frac{1}{2} < 1$ . ✓ Why this step? Regularity (the condition we defined above) guarantees the geometric series of level-costs shrinks going down, so it converges to the top term instead of blowing up.
Apply Case 3. $T (n) = Θ (f (n)) = Θ (n^{2})$ .

Verify: the root alone costs $n^{2}$ , and each lower level costs at most half the one above ( $\frac{1}{2}, \frac{1}{4}, \dots$ ), a decreasing Geometric Series summing to $\leq 2 n^{2}$ . So total $= Θ (n^{2})$ . ✓

Worked example

Example 6 — Cell E (regularity FAILS) · $T (n) = 2 T (n /2) + n^{2} ∣ sin n ∣$ ⚠ Forecast: $f$ looks bigger than the $n^{1}$ ruler, so you may reach for Case 3. Pause — is it always bigger?

Read off constants. $a = 2, b = 2$ , and $f (n) = n^{2} ∣ sin n ∣$ , leaf ruler $n^{1}$ . Why this step? Even for a trap recurrence, naming $a, b, f$ and the ruler is where we start.
Try the $Ω$ condition. $∣ sin n ∣$ dips arbitrarily close to $0$ , so $f (n)$ is not bounded below by $n^{1 + ϵ}$ at those points. Why this step? Case 3 needs $f = Ω (n^{l o g_{b} a + ϵ})$ for all large $n$ ; an oscillating $f$ breaks this lower bound.
Try regularity anyway. $a f (n / b) = 2 \cdot \frac{n ^{2}}{4} ∣ sin (n /2)∣ = \frac{n ^{2}}{2} ∣ sin (n /2)∣$ . Because $sin (n /2)$ and $sin n$ are uncorrelated in sign/size, no fixed $c < 1$ makes $a f (n / b) \leq c f (n)$ hold for all large $n$ . Why this step? If regularity can fail infinitely often, the level-cost series need not converge to the root — so Case 3's conclusion is unjustified.
Verdict. The basic Master Theorem does not apply. Fall back to a recursion tree bound or Akra–Bazzi method, which handle irregular $f$ .

Verify: this is a negative result — the check is that the two Case-3 preconditions genuinely fail, which we showed in steps 2–3. Lesson: a bigger-looking $f$ is not enough; you must earn Case 3 twice. ✓ (nothing numeric to plug)

Worked example

Example 7 — Cell F (the log-gap trap) · $T (n) = 2 T (n /2) + n lo g n$ Forecast: $n lo g n$ is bigger than the ruler $n$ … so Case 3, answer $n lo g n$ ? Write that tempting guess down — then watch it fail.

Read off constants. $a = 2, b = 2, f (n) = n lo g n$ ; ruler $= n^{l o g_{2} 2} = n$ . Why this step? Name $a, b, f$ and build the ruler before judging the gap.
Test Case 3's $Ω$ . Is $n lo g n = Ω (n^{1 + ϵ})$ for some $ϵ > 0$ ? No! For any $ϵ > 0$ , $n^{ϵ}$ eventually beats $lo g n$ , so $n lo g n$ is smaller than $n^{1 + ϵ}$ . The gap is only a log, not a polynomial. Why this step? Case 3 demands a polynomial margin ( $Ω$ with a real exponent). A log margin lands in the crack between the cases.
Recognize extended Case 2. $f (n) = n lo g n = Θ (n^{1} lo g^{1} n)$ , so $k = 1$ . Why this step? Extended Case 2 is exactly the tool for $f = Θ (n^{l o g_{b} a} lo g^{k} n)$ — it fills the crack the basic three cases leave open.
Apply. $T (n) = Θ (n lo g^{k + 1} n) = Θ (n lo g^{2} n)$ .

Verify: the level-costs are $n lo g n, n lo g (n /2), \dots$ — nearly equal across all $lo g_{2} n$ levels. Summing $\approx n lo g n$ over $lo g n$ levels gives $\sim n lo g^{2} n$ . The naive " $n lo g n$ " undercounts by a whole log factor. ✓

Worked example

Example 8 — Cell G (real-world word problem) "A photo-sharing app builds a thumbnail collage. To render a collage of $n$ photos it splits the photos into $3$ equal groups, recursively renders each group's sub-collage, then stitches the $3$ results with an edge-blend that costs $Θ (n)$ per stitch. What is the render time?"

Forecast: three sub-jobs, each a third the size, linear stitch. Guess before computing.

Translate prose to $a, b, f$ . "split into $3$ groups" → $a = 3$ . "each a third the size" → $b = 3$ . "stitch costs $Θ (n)$ " → $f (n) = n$ . Why this step? The hard part of word problems is reading off the recurrence; the algebra is easy once $a, b, f$ are named.
Write the recurrence. $T (n) = 3 T (n /3) + n$ . Why this step? Getting to the standard form $a T (n / b) + f (n)$ is what lets the theorem apply at all.
Compute the leaf exponent. $lo g_{3} 3 = 1$ , leaf cost $= n$ . Why this step? Build the ruler so we can compare the linear stitch against it.
Compare. $f (n) = n = Θ (n^{1} lo g^{0} n)$ — an exact tie ( $Θ$ ), $k = 0$ → Case 2. Why this step? Same drill as Example 3; the tie means every floor costs the same $Θ (n)$ .
Answer. $T (n) = Θ (n lo g n)$ . The app renders in $n lo g n$ time — same class as Merge Sort.

Verify: at $n = 27$ : $lo g_{3} 27 = 3$ floors, each $\approx 27$ , total $\approx 81$ ; and $n lo g_{3} n = 27 \times 3 = 81$ . Matches. ✓

Worked example

Example 9 — Cell H (exam twist: looks like Case 1, is Case 2) · $T (n) = 4 T (n /2) + n^{2} / lo g n$ Forecast: $n^{2} / lo g n$ is smaller than the ruler $n^{2}$ — so Case 1, answer $n^{2}$ ? That's the bait.

Read off constants. $a = 4, b = 2$ ; $f (n) = n^{2} / lo g n$ . Why this step? Name $a, b, f$ first — the twist hides in $f$ , so we must see it plainly.
Compute the leaf exponent. $lo g_{2} 4 = 2$ , ruler $= n^{2}$ . Why this step? We need the ruler to measure how far $f$ sits below it — and whether that gap is polynomial or just a log.
Test Case 1's $O$ . Case 1 needs $f = O (n^{2 - ϵ})$ — smaller by a polynomial. But $n^{2} / lo g n$ is only smaller by a log, not a power ( $n^{2 - ϵ}$ eventually beats $n^{2} / lo g n$ from below). So Case 1 does not apply. Why this step? Just like Example 7 but mirrored — the gap between $f$ and the ruler is a log, so the basic case's polynomial requirement fails.
Read it as extended Case 2 with negative $k$ . $f (n) = n^{2} lo g^{- 1} n = Θ (n^{2} lo g^{- 1} n)$ , i.e. $k = - 1$ . Why this step? Extended Case 2 permits $k = - 1$ (a special sub-case): when $k = - 1$ the answer is $Θ (n^{l o g_{b} a} lo g lo g n)$ , not the usual $lo g^{k + 1} n$ .
Apply the $k = - 1$ rule. $T (n) = Θ (n^{2} lo g lo g n)$ .

Verify: the level costs form the series $\sum \frac{n ^{2}}{l o g ( n / 2 ^{i} )}$ , and summing $1/ lo g$ terms over $lo g n$ levels grows like $lo g lo g n$ (a harmonic-of-logs sum), giving $n^{2} lo g lo g n$ — strictly above the naive $n^{2}$ of the Case-1 trap. ✓

What every cell taught you

Recall One-line lesson per cell (click to reveal)

A: many subproblems, cheap combine → count leaves, $Θ (n^{l o g_{b} a})$ .
A′: constant $f$ with $a > 1$ → leaves still win, $Θ (n^{l o g_{b} a})$ (Case 1).
B: $f$ equals the ruler → tie → $\times lo g n$ .
C: $a = 1$ single stick, ruler is $1$ → $Θ (lo g n)$ .
D: big $f$ and regularity → $Θ (f)$ .
E: big-looking but oscillating $f$ → theorem refuses; use Akra–Bazzi.
F: bigger only by a log → extended Case 2, extra $lo g$ .
G: word problems = translate to $a, b, f$ first, then it's routine.
H: smaller only by a log → still Case 2 ( $k = - 1$ ), $Θ (n^{l o g_{b} a} lo g lo g n)$ .

Connections

Parent topic
Recursion Trees — the fallback when a cell (like E) breaks the theorem.
Akra–Bazzi method — handles the oscillating- $f$ Example 6.
Big-O, Big-Omega, Big-Theta — the $O /Ω/Θ$ language every comparison used.
Geometric Series — why leaves/tie/root correspond to shrinking/flat/growing series.
Merge Sort, Binary Search, Karatsuba Multiplication — real algorithms behind cells B, C, A.