Divide and conquer — template, correctness, recurrence: Worked examples

This page is a drill. The parent note built the machinery — the template, the recurrence $T (n) = a T (n / b) + f (n)$ , and the Master Theorem. Here we throw every kind of input at that machinery and grind out the answer, so that when an exam or a real problem hands you a recurrence, you have already seen its shape.

Before we start, one reminder of what each letter means, because we will not re-derive it — we will use it every single time:

Recall The numbers you always read off first

Question ::: In $T (n) = a T (n / b) + f (n)$ , what are $a$ , $b$ , $f$ ? $a$ ::: how many subproblems each call spawns $b$ ::: the factor the input shrinks by (size goes $n \to n / b$ ) $f (n)$ ::: the non-recursive work — divide cost plus combine cost $c_{crit}$ ::: the derived watershed exponent $lo g_{b} a$ , i.e. the cost of the leaves $n^{l o g_{b} a}$ (computed from $a, b$ , not read off)

The whole game is: compute $c_{crit} = lo g_{b} a$ , then compare $f (n)$ against $n^{c_{crit}}$ . Three outcomes are possible — $f$ smaller, $f$ equal, $f$ bigger — and there are also degenerate recurrences where this comparison does not even apply. That is exactly our matrix.

The scenario matrix

Every divide-and-conquer recurrence you meet falls into one of these cells. The columns are how $f$ sits relative to the watershed $n^{l o g_{b} a}$ ; the rows are the special / degenerate inputs that break the naive routine.

Cell	What makes it this cell	Example we work
A — Balanced (Case 2)	$f (n) = Θ (n^{l o g_{b} a})$ : divide-cost matches leaf-cost	Ex 1 (Mergesort), Ex 8 (word problem)
B — Leaf-heavy (Case 1)	$f (n)$ is polynomially smaller than $n^{l o g_{b} a}$	Ex 2 (Karatsuba)
C — Root-heavy (Case 3)	$f (n)$ is polynomially bigger, plus regularity holds	Ex 3
D — Single subproblem ( $a = 1$ )	tree is a chain, $c_{crit} = 0$	Ex 4 (Binary Search)
E — Uneven / degenerate split	subproblem sizes differ, or one is size $0$ ; shrink is not a constant factor ( $b \to 1$ ), so floors/ceilings can no longer be waved away	Ex 5 (bad Quicksort pivot)
F — Basic Master Theorem fails	$f$ only a log factor off the watershed — needs the extended rule or the tree	Ex 6
G — Regularity fails	$f$ looks root-heavy but $a f (n / b) \neq \leq k f (n)$	Ex 7
H — Exam twist	$n$ shrink / disguised recurrence	Ex 8 (word problem), Ex 9

We now hit every cell.

Cell A — Balanced (Master Theorem Case 2)

Worked example Ex 1 — Mergesort, the archetype

Solve $T (n) = 2 T (n /2) + Θ (n)$ .

Forecast: guess the growth before reading on. Two half-size sorts plus a linear merge — faster than $n^{2}$ ? Slower than $n$ ?

Read off $a, b, f$ . Here $a = 2$ (two halves), $b = 2$ (each is $n /2$ ), $f (n) = Θ (n)$ . Why this step? Everything downstream is a comparison, and you cannot compare until you have these three numbers.
Compute the watershed $c_{crit} = lo g_{b} a = lo g_{2} 2 = 1$ , so the leaf cost is $n^{1} = n$ . Why this step? $n^{c_{crit}}$ is the single yardstick we hold $f (n)$ up against.
Compare. $f (n) = Θ (n) = Θ (n^{1}) = Θ (n^{c_{crit}})$ — an exact tie. That is the definition of Case 2. Why this step? A tie means no level of the recursion tree dominates; every level does the same $Θ (n)$ work.
Apply Case 2: $T (n) = Θ (n^{c_{crit}} lo g n) = Θ (n lo g n)$ . Why this step? There are $lo g_{2} n$ levels (see figure below) and each costs $Θ (n)$ ; equal work $\times$ number of levels $=$ multiply.

Verify: count the levels directly. At depth $i$ there are $2^{i}$ nodes each of size $n / 2^{i}$ , so level work $= 2^{i} \cdot (n / 2^{i}) = n$ . Number of levels until size $1$ : $lo g_{2} n$ . Total $= n lo g_{2} n$ . ✓ Matches. See Mergesort and Recurrence Relations.

Figure — Divide and conquer — template, correctness, recurrence

Read the figure: each row is one level of recursion. The black dots are the subproblems; the red label on the right shows their total work. Notice the punchline — although the dots double every level and shrink by half, their widths cancel, so every red label reads $n$ . There are $lo g_{2} n$ rows (the black double-arrow on the left), and $n$ work per row times $lo g_{2} n$ rows is exactly the $Θ (n lo g n)$ we computed.

Cell B — Leaf-heavy (Master Theorem Case 1)

Worked example Ex 2 — Karatsuba multiplication

Solve $T (n) = 3 T (n /2) + Θ (n)$ .

Forecast: three half-size multiplies instead of the schoolbook four. Below $n^{2}$ ? By how much?

Read off: $a = 3$ , $b = 2$ , $f (n) = Θ (n)$ . Why this step? Same first move as always — you cannot pick a Master-Theorem case without the three numbers, and here $a = 3$ (three products) is the whole novelty, so pin it down first.
Watershed: $c_{crit} = lo g_{2} 3 \approx 1.585$ . Leaf cost $n^{1.585}$ . Why this step? Here $a \neq = b$ , so the exponent is not a clean integer — you must actually take a log rather than eyeballing it.
Compare. Pick the representative $n$ from the class $f (n) = Θ (n)$ (any function in the class compares the same way). Is $n$ smaller than $n^{1.585}$ ? Yes, and polynomially so: $n = n^{1.585 - ε}$ with $ε \approx 0.585 > 0$ . That is Case 1. Why this step? Case 1 needs the gap to be a genuine power of $n$ (not just a log factor); $0.585$ is a fat polynomial gap, so we are safe.
Apply Case 1: the leaves swamp everything, $T (n) = Θ (n^{l o g_{2} 3}) \approx Θ (n^{1.585})$ .

Verify: the leaf term alone is $n^{l o g_{2} 3} = n^{1.585}$ ; the summed non-recursive work is a geometric series with ratio $a / b = 3/2 > 1$ , dominated by its last (leaf) term — so total $= Θ (n^{1.585})$ . And $1.585 < 2$ , beating schoolbook. ✓ See Karatsuba.

Cell C — Root-heavy (Master Theorem Case 3)

Worked example Ex 3 — a divide with expensive combine

Solve $T (n) = 2 T (n /2) + Θ (n^{2})$ .

Forecast: the combine step $n^{2}$ is heavy. Does the recursion still matter, or does the top call dominate?

Read off: $a = 2$ , $b = 2$ , $f (n) = Θ (n^{2})$ . Why this step? The one heavy ingredient here is $f (n) = n^{2}$ — an expensive combine — so we identify it explicitly before testing which side of the watershed it lands on.
Watershed: $c_{crit} = lo g_{2} 2 = 1$ , leaf cost $n^{1}$ . Why this step? We need the yardstick $n^{c_{crit}} = n^{1}$ in hand to see that the combine cost $n^{2}$ towers over it.
Compare: $f (n) = n^{2}$ vs $n^{1}$ . Now $f$ is bigger, polynomially: $n^{2} = n^{1 + ε}$ with $ε = 1 > 0$ . Candidate Case 3. Why this step? Case 3 is the "root dominates" case; before we may claim it we must confirm $f$ beats the leaves by an honest power of $n$ , and $ε = 1$ is exactly that confirmation.
Check the regularity condition $a f (n / b) \leq k f (n)$ for some $k < 1$ : $2 \cdot (\frac{n}{2})^{2} = 2 \cdot \frac{n ^{2}}{4} = \frac{n ^{2}}{2} = \frac{1}{2} f (n) .$ So $k = \frac{1}{2} < 1$ . ✓ Regularity holds. Why this step? Case 3 is a promise that work shrinks going down the tree; regularity is the proof of that promise. Skip it and you can be wrong (see Ex 7).
Apply Case 3: $T (n) = Θ (f (n)) = Θ (n^{2})$ .

Verify: the per-level work is $n^{2}, \frac{n ^{2}}{2}, \frac{n ^{2}}{4}, \dots$ — a geometric series with ratio $\frac{1}{2}$ , summing to $2 n^{2} = Θ (n^{2})$ , dominated by the root. ✓

Read the figure: each bar is the total work at one recursion level, measured in units of $n^{2}$ . Unlike Ex 1's flat profile, here the bars shrink geometrically — each is half the previous. The tall red bar at depth $0$ is the root, and because the bars fall off so fast, the entire tower sums to just $2 \times$ that first bar. That is what "the root dominates" looks like, and it is why the answer is $Θ (n^{2})$ , the cost of the root alone.

Cell D — Single subproblem ( $a = 1$ )

Worked example Ex 4 — Binary search

Solve $T (n) = T (n /2) + Θ (1)$ .

Forecast: you throw away half the array and never look back. How many steps?

Read off: $a = 1$ , $b = 2$ , $f (n) = Θ (1)$ . Why this step? Notice $a = 1$ : each call makes one recursive call, so the "tree" is a single vertical chain, not a branching tree.
Watershed: $c_{crit} = lo g_{2} 1 = 0$ , leaf cost $n^{0} = 1$ . Why this step? $lo g$ of $1$ is $0$ — the leaves cost a constant, not a power of $n$ . That is what makes single-subproblem recurrences so cheap.
Compare: $f (n) = Θ (1) = Θ (n^{0}) = Θ (n^{c_{crit}})$ — a tie, Case 2. Why this step? We hold $f$ up against the yardstick $n^{c_{crit}} = n^{0} = 1$ ; both are constant, so neither the root nor the leaves dominate — the hallmark of Case 2.
Apply Case 2: $T (n) = Θ (n^{0} lo g n) = Θ (lo g n)$ . Why this step? Case 2 multiplies the leaf cost by the number of levels; with leaf cost $n^{0} = 1$ and $lo g n$ levels, the product is exactly $Θ (lo g n)$ .

Verify: the chain has length "how many times can you halve $n$ to reach $1$ " $= lo g_{2} n$ , each doing $Θ (1)$ work → $Θ (lo g n)$ . ✓ See Binary Search.

Read the figure: because $a = 1$ , the picture is a single vertical stack, not a branching tree — one dot per level, each labelled with its shrinking size ( $n, n /2, n /4, \dots$ ) and its constant $O (1)$ work. The red dot at the bottom is the base case, size $1$ . The black double-arrow counts the rungs: $lo g_{2} n$ of them, each doing $O (1)$ , so the total is $Θ (lo g n)$ .

Cell E — Uneven / degenerate split

Worked example Ex 5 — Quicksort's worst pivot (a size-

$0$ subproblem) A bad pivot puts everything on one side. The recurrence becomes $T (n) = T (n - 1) + T (0) + Θ (n) .$ Solve it.

Forecast: the split is $n - 1$ and $0$ — the "divide" barely shrinks. Is this still $n lo g n$ ? Or worse?

Collapse the size- $0$ term. By our base-case convention $T (0) = Θ (1)$ , so it is absorbed into the $Θ (n)$ non-recursive work: $T (n) = T (n - 1) + Θ (1) + Θ (n) = T (n - 1) + Θ (n) .$ Why this step? A subproblem of size $0$ does no recursion — it just returns a constant. Naming that constant explicitly ( $T (0) = Θ (1)$ ) is what lets us drop it into the $Θ (n)$ term instead of leaving a mysterious second recursive call.
Spot the degeneracy. The surviving subproblem has size $n - 1$ : the shrink is $n \to n - 1$ , i.e. $b \to 1$ . Master Theorem does not apply. Why this step? $lo g_{b} a$ blows up as $b \to 1$ ; the whole comparison framework assumes a constant-factor shrink, which we do not have. This is also the one place the floor/ceiling rescue from the top of the page fails — the input drops by an additive $1$ , not a multiplicative factor.
Unroll by hand instead: $T (n) = Θ (n) + Θ (n - 1) + \dots + Θ (1) = Θ (\sum_{k = 1}^{n} k) .$ Why this step? When the shortcut is void, go back to the definition: a recurrence is just an instruction to substitute itself into itself. Expanding $T (n) = T (n - 1) + Θ (n)$ repeatedly is that substitution, and it exposes one $Θ (n), Θ (n - 1), \dots$ term per level — a sum we can evaluate directly.
Sum the arithmetic series: $\sum_{k = 1}^{n} k = \frac{n ( n + 1 )}{2} = Θ (n^{2})$ . Why this step? The chain of substitutions produced a plain arithmetic series; Gauss's closed form $\frac{n ( n + 1 )}{2}$ turns it into a clean $Θ$ -class.
Conclude $T (n) = Θ (n^{2})$ .

Verify: for $n = 4$ : $4 + 3 + 2 + 1 = 10 = \frac{4 \cdot 5}{2}$ . ✓ Worst-case Quicksort really is quadratic — this cell is why pivot choice matters.

Cell F — Basic Master Theorem fails (the log-factor gap)

Worked example Ex 6 — a recurrence between Case 2 and Case 3

Solve $T (n) = 2 T (n /2) + Θ (n lo g n)$ .

Forecast: $n lo g n$ is just barely above $n$ . Which case? (Trick question.)

Read off $a, b$ and the watershed: $a = 2$ , $b = 2$ , $c_{crit} = lo g_{2} 2 = 1$ , leaf cost $n^{1}$ ; and $f (n) = Θ (n lo g n)$ . Why this step? Same opening move as always — no case can be chosen without $a$ , $b$ , and the derived $c_{crit}$ in hand, so we pin them down first and note that here $f$ carries an extra $lo g n$ over the plain $n$ .
Compare: $f (n) = n lo g n$ vs $n^{1}$ . Is $f$ polynomially bigger, i.e. $n lo g n \geq n^{1 + ε}$ for some fixed $ε > 0$ ? No — $lo g n$ grows slower than any power $n^{ε}$ . So $f$ is bigger by only a log factor, not a polynomial factor. Why this step? The basic three-case Master Theorem demands a polynomial gap for Cases 1 and 3. A log-sized gap falls into a crack the basic version cannot cover.
Reach for the tool that fits. Two clean options handle this exact crack:
- The extended Master Theorem covers $f (n) = Θ (n^{c_{crit}} lo g^{k} n)$ for integer $k \geq 0$ , giving $T (n) = Θ (n^{c_{crit}} lo g^{k + 1} n)$ . Here $k = 1$ , so $T (n) = Θ (n lo g^{2} n)$ immediately.
- Or fall back to the recursion tree for a first-principles derivation. Level $i$ cost: $2^{i} \cdot f (\frac{n}{2 ^{i}}) = 2^{i} \cdot \frac{n}{2 ^{i}} lo g \frac{n}{2 ^{i}} = n lo g \frac{n}{2 ^{i}} = n (lo g n - i) .$ Why this step? The tree method never fails — it computes each level's work from the raw recurrence with no case analysis. We reach for it (or the extended rule) precisely because the basic three-case version refused to fire.
Sum the tree over $i = 0$ to $lo g_{2} n$ : $\sum_{i = 0}^{l o g_{2} n} n (lo g n - i) = n \sum_{j = 0}^{l o g_{2} n} j = n \cdot Θ (lo g^{2} n) = Θ (n lo g^{2} n) .$ Why this step? The inner sum $0 + 1 + \dots + lo g n$ is an arithmetic series $Θ (lo g^{2} n)$ — and it agrees with the extended-rule answer, confirming both.
Conclude $T (n) = Θ (n lo g^{2} n)$ .

Verify: at $n = 8$ (so $lo g_{2} n = 3$ ): levels cost $n (3 - 0), n (3 - 1), n (3 - 2), n (3 - 3) = 24, 16, 8, 0$ , sum $= 48 = 8 \cdot 6 = n \cdot \frac{3 \cdot 4}{2}$ , matching $n \cdot Θ (lo g^{2} n)$ . ✓

Cell G — Regularity fails (root-heavy in shape only)

Worked example Ex 7 — why you cannot skip the regularity check

This cell contrasts two recurrences that both look root-heavy. Case (i) passes regularity and is solved cleanly; case (ii) fails it and shows why the check matters.

Forecast: both have an $f$ far above $n^{1}$ . Surely both are Case 3?

Case (i): $T (n) = 2 T (n /2) + \frac{n ^{2}}{lo g n}$ — solve it fully.

Watershed: $c_{crit} = lo g_{2} 2 = 1$ , leaf cost $n^{1}$ . Why this step? Same yardstick as always; we must know $n^{1}$ to judge $n^{2} / lo g n$ .
Polynomial-gap test: is $\frac{n ^{2}}{l o g n} \geq n^{1 + ε}$ for a fixed $ε > 0$ ? Take $ε = \frac{1}{2}$ : we need $\frac{n ^{2}}{l o g n} \geq n^{1.5}$ , i.e. $n^{0.5} \geq lo g n$ — true for all large $n$ . So yes, $f$ is polynomially above the watershed → candidate Case 3. Why this step? Case 3 first demands a genuine power-of- $n$ gap; the $lo g$ in the denominator is harmless because $n^{0.5}$ eventually dwarfs it.
Regularity check $2 f (n /2) \leq k f (n)$ : $2 \cdot \frac{( n /2 ) ^{2}}{l o g ( n /2 )} = \frac{n ^{2} /2}{l o g n - 1} \leq k \cdot \frac{n ^{2}}{l o g n} .$ For large $n$ , $\frac{l o g n}{2 ( l o g n - 1 )} \to \frac{1}{2} < 1$ , so a valid $k < 1$ exists. ✓ Regularity holds. Why this step? Regularity guarantees the per-level work decays geometrically, which is exactly what lets the root dominate.
Conclude (i): Case 3 fires, $T (n) = Θ (\frac{n ^{2}}{lo g n})$ .

Case (ii): $T (n) = 2 T (n /2) + f (n)$ with $f (n) = n^{2} cos^{2} n$ — the trap.

Same size test: $f (n)$ reaches up to $n^{2}$ , which is $Ω (n^{1.5})$ along the peaks — it looks root-heavy.
Regularity fails. Because $cos^{2} n$ dips to $0$ infinitely often, there is no single $k < 1$ with $2 f (n /2) \leq k f (n)$ for all $n$ : at an $n$ where $f (n) \approx 0$ but $f (n /2)$ is near its peak, the inequality is violated outright. Why this step? Regularity is the promise "work decays down the tree." An oscillating $f$ breaks that promise, so "the root dominates" is simply false, and Case 3 offers no conclusion.
Conclude (ii): the Master Theorem says nothing here; you would fall back to the tree or Akra–Bazzi (Ex 6's box).

Verify (numeric, on case (i) at $n = 16$ ): check $2 f (n /2) \leq f (n)$ , i.e. $k$ ratio $< 1$ : $2 \cdot \frac{( 16/2 ) ^{2}}{l o g _{2} ( 16/2 )} = \frac{128}{3} \approx 42.67, f (16) = \frac{256}{4} = 64, ratio \approx 0.667 < 1.$ ✓ Regularity holds at $n = 16$ — but only because we checked it.

Cell A / H — Real-world word problem

Worked example Ex 8 — Tournament: finding the champion

$n = 1, 024$ players. A match compares two players in $1$ unit of time; the winner advances. You organise a knockout bracket: split the field in half, find the champion of each half recursively, then play one final match. How long to crown a champion?

Forecast: knockout of $1024$ players — closer to $10$ matches deep or $1000$ matches total?

Model as a recurrence. Two halves of size $n /2$ ( $a = 2, b = 2$ ), combine = the single final match, cost $Θ (1)$ : $T (n) = 2 T (n /2) + Θ (1) .$ Why this step? "Split, recurse on each half, one merge match" is the divide-and-conquer template verbatim — turning the story into $a, b, f$ is the only way to reuse the machinery.
Watershed: $c_{crit} = lo g_{2} 2 = 1$ , leaf cost $n^{1}$ . Why this step? We need $n^{1}$ to see that the cheap $Θ (1)$ combine sits below it.
Compare: $f (n) = Θ (1) = Θ (n^{0})$ , which is below $n^{1}$ polynomially ( $ε = 1$ ) → Case 1. Why this step? Here the combine is cheap but the branching is rich — the leaves (the $n$ first-round players) dominate.
Apply Case 1: $T (n) = Θ (n^{1}) = Θ (n)$ . Concretely, a knockout on $n$ players needs exactly $n - 1$ matches (each match eliminates one player, and $n - 1$ must be eliminated).

Verify: $n = 1024 \Rightarrow n - 1 = 1023$ matches total. The bracket depth is $lo g_{2} 1024 = 10$ rounds — but total work is $Θ (n) = 1023$ , matching Case 1, not $Θ (lo g n)$ . ✓

Cell H — Exam twist ( $n$ shrink)

Worked example Ex 9 — the change-of-variable trick

Solve $T (n) = 2 T (n) + Θ (lo g n)$ .

Forecast: the input shrinks by a square root, not a constant factor. Master Theorem wants $n / b$ — this is not that shape. What now?

Substitute $m = lo g_{2} n$ , i.e. $n = 2^{m}$ . Then $n = 2^{m /2}$ , so $T (n)$ becomes $T (2^{m /2})$ . Let $S (m) = T (2^{m})$ : $S (m) = 2 S (m /2) + Θ (m) .$ Why this step? A $n$ shrink is not a constant factor, so no $b$ exists and the Master Theorem is stuck. But $n$ halves the exponent of $n$ . If we make the exponent our new variable $m$ , the ugly square root becomes a clean division by $2$ — restoring the exact $S (m) = 2 S (m /2) + \dots$ shape the theorem was built for. Change of variable is the standard move whenever the shrink is multiplicative in the exponent rather than in $n$ .
Solve $S (m) = 2 S (m /2) + Θ (m)$ . This is exactly Ex 1 (Mergesort's shape): $a = 2, b = 2, c_{crit} = 1$ , $f (m) = Θ (m)$ → Case 2 → $S (m) = Θ (m lo g m)$ . Why this step? We deliberately transformed the problem into one we have already solved, so we simply quote Ex 1 rather than redo the tree.
Substitute back $m = lo g n$ : $T (n) = S (lo g n) = Θ (lo g n \cdot lo g lo g n) .$ Why this step? We defined $S (m) = T (2^{m})$ , so $T (n) = S (lo g_{2} n)$ ; plug $m = lo g n$ into $m lo g m$ to return to the original variable.

Verify: take $n = 2^{16}$ , so $m = lo g_{2} n = 16$ .

Via $S$ : $S (16) = 16 \cdot lo g_{2} 16 = 16 \cdot 4 = 64$ .
Via the final formula: $lo g_{2} n \cdot lo g_{2} (lo g_{2} n) = 16 \cdot lo g_{2} 16 = 16 \cdot 4 = 64$ .

Both routes give $64$ , so $T (2^{16}) = S (16)$ and the change of variable is consistent. ✓ The closed form $T (n) = Θ (lo g n \cdot lo g lo g n)$ checks out.

Recall Self-test

$T (n) = 4 T (n /2) + n^{2}$ solves to? ::: $c_{crit} = lo g_{2} 4 = 2$ , $f = n^{2}$ ties → Case 2 → $Θ (n^{2} lo g n)$ $T (n) = T (n - 1) + 1$ solves to? ::: not Master-able ( $b \to 1$ ); unroll → $Θ (n)$ Why does the tournament give $Θ (n)$ not $Θ (lo g n)$ ? ::: the depth is $lo g n$ , but total work (leaves) dominates → $n - 1$ matches

Related paradigms build on this same recurrence machinery: Strassen Matrix Multiplication (a Case-1 win like Karatsuba), Mathematical Induction (the correctness engine), and Dynamic Programming (what you reach for when subproblems overlap instead of being independent).