Substitution method for recurrences: Worked examples

Before anything else, one word we will lean on constantly:

Everything below is just: compute $R (n)$ , then ask "can I make it $\leq 0$ ?".

The scenario matrix

Recurrences vary along a few independent axes. Each cell is a combination we must be able to handle. Read the table as "here are all the traps; each example disarms one."

Cell	Case class	What makes it distinct	Disarmed by
C1	Clean absorb, upper bound $O$	residual goes $\leq 0$ with any $c \geq$ something	Example 1
C2	Lower bound $Ω$	inequality flips: need $R (n) \geq 0$	Example 2
C3	Guess too tight (fails)	residual is forced positive — proof must be rejected	Example 3
C4	Stubborn residual → strengthen hypothesis	naive $c n$ leaves a constant; subtract $- d$	Example 4
C5	Unequal splits $n / b_{1} + n / b_{2}$	two different smaller sizes	Example 5
C6	Subtractive recurrence $T (n - 1)$	shrinks by subtraction, not division	Example 6
C7	Changing variables (weird argument like $n$ )	substitution needs a variable swap first	Example 7
C8	Degenerate / base-case pitfall ( $lo g 1 = 0$ , $n_{0}$ choice)	the induction has no ground floor	Example 8
C9	Real-world word problem	a story that hides a recurrence	Example 9
C10	Exam twist: floors/ceilings & off-by-constant	$⌈ n /2 ⌉$ instead of $n /2$	Example 10

Ten cells, ten examples. Let us go.

Example 1 — Cell C1: clean absorb, upper bound

Worked example Prove

$T (n) = 3 T (n /4) + n \leq c n$ , i.e. $T (n) = O (n)$ . Forecast: each level spends $n$ work but the three subproblems are each only a quarter the size. Do you think the total stays linear, or blows up to $n lo g n$ ? Guess before reading.

Step 1 — Guess. $T (n) \leq c n$ for some $c > 0$ and all $n \geq n_{0}$ . Why this step? Linear is the smallest sensible guess; if it survives we are done, if it fails we learn the true growth.

Step 2 — Assume (IH). For every $k < n$ , assume $T (k) \leq c k$ . In particular $T (n /4) \leq c \frac{n}{4}$ . Why this step? $n /4 < n$ , so induction lets us take the claim for granted there.

Step 3 — Substitute. $T (n) = 3 T (n /4) + n \leq 3 (c \frac{n}{4}) + n = \frac{3}{4} c n + n .$ Why this step? Replacing $T (n /4)$ by its assumed upper bound can only raise the right side — legal for an upper bound.

Step 4 — Find the residual. Write it as goal + residual: $\frac{3}{4} c n + n = goal c n + R (n) (- \frac{1}{4} c n + n) .$ So $R (n) = n (1 - \frac{c}{4})$ . Why this step? This is the whole game — expose what stands between us and $c n$ .

Step 5 — Absorb. We need $R (n) \leq 0$ , i.e. $1 - \frac{c}{4} \leq 0$ , i.e. $c \geq 4$ . Choose $c = 4$ . Why this step? A single fixed $c = 4$ makes the residual non-positive for all $n$ — that reproduces the same $c$ we assumed.

Step 6 — Base case. At $n = 1$ : $T (1)$ is some constant, and $c n = 4 \cdot 1 = 4$ . Pick $c = max (4, T (1))$ so $T (1) \leq c$ . Why this step? Induction with no ground floor proves nothing. Here $f (n) = n > 0$ at $n = 1$ , so no $lo g 1$ trap.

Verify: with $c = 4$ : $\frac{3}{4} (4) n + n = 3 n + n = 4 n = c n$ . ✓ Residual is exactly $0$ at the boundary $c = 4$ , negative for larger $c$ . Forecast check: it stays linear because $3/4 < 1$ shrinks the work geometrically down the tree — matches Master Theorem Case 3 intuition.

Example 2 — Cell C2: lower bound $Ω$ (the inequality flips)

Worked example Prove

$T (n) = 2 T (n /2) + n \geq c n lo g_{2} n$ , i.e. $T (n) = Ω (n lo g n)$ . Forecast: for an upper bound we needed the residual $\leq 0$ . For a lower bound, guess what flips.

Step 1 — Guess. $T (n) \geq c n lo g_{2} n$ . Why this step? $Ω$ asks for a floor, not a ceiling, so we now chase a $\geq$ .

Step 2 — Assume (IH). $T (n /2) \geq c \frac{n}{2} lo g_{2} \frac{n}{2}$ . Why this step? $n /2 < n$ ; the lower-bound IH is assumed for smaller inputs.

Step 3 — Substitute. $T (n) = 2 T (n /2) + n \geq 2 (c \frac{n}{2} lo g_{2} \frac{n}{2}) + n = c n lo g_{2} \frac{n}{2} + n .$ Why this step? Replacing $T (n /2)$ by a lower bound can only lower the right side — legal for a $\geq$ chain.

Step 4 — Massage & residual. Use $lo g_{2} \frac{n}{2} = lo g_{2} n - 1$ : $c n (lo g_{2} n - 1) + n = goal c n lo g_{2} n + R (n) (n - c n) .$ So $R (n) = n (1 - c)$ . Why this step? For $Ω$ , the win condition is $R (n) \geq 0$ (we must not fall below the goal).

Step 5 — Absorb (flipped). Need $1 - c \geq 0$ , i.e. $c \leq 1$ . Choose $c = 1$ . Why this step? Notice the direction reversed vs. Example 1: an upper bound wants a big $c$ , a lower bound wants a small $c$ .

Step 6 — Base case. At $n = 2$ : $c n lo g_{2} n = 1 \cdot 2 \cdot 1 = 2$ . As long as $T (2) \geq 2$ (true for a real algorithm doing $\geq 2$ work), grounded. Why this step? Choose $n_{0} = 2$ so $lo g_{2} n_{0} = 1 \neq = 0$ .

Verify: with $c = 1$ : $1 \cdot n (lo g_{2} n - 1) + n = n lo g_{2} n - n + n = n lo g_{2} n$ . ✓ Combined with Example 1's style upper bound, $T (n) = Θ (n lo g n)$ — the Merge Sort Analysis classic.

Example 3 — Cell C3: the guess is too tight (a correct rejection)

Worked example Attempt

$T (n) = 2 T (n /2) + n \leq c n$ . Show this guess is wrong. Forecast: we already suspect the answer is $n lo g n$ . So the linear guess should fail. Predict how the residual misbehaves.

Step 1 — Guess. $T (n) \leq c n$ . Why this step? Deliberately too tight — we want to see the failure signature so we recognise it in exams.

Step 2 — Assume. $T (n /2) \leq c \frac{n}{2}$ .

Step 3 — Substitute. $T (n) \leq 2 (c \frac{n}{2}) + n = c n + n .$ Why this step? Straight plug-in.

Step 4 — Residual. $c n + n = goal c n + R (n) n, R (n) = n .$ Why this step? Here is the tell: the residual is $+ n$ , a positive quantity that grows with $n$ .

Step 5 — Try to absorb. We need $R (n) = n \leq 0$ . Impossible for $n \geq 1$ for any constant $c$ — $c$ never touches the residual. Why this step? This is Mistake A from the parent: you might be tempted to say " $(c + 1) n$ is still $O (n)$ ", but induction must reproduce the same $c$ . It cannot.

Conclusion: the guess $O (n)$ is rejected. The extra $+ n$ per level accumulates over $lo g_{2} n$ levels → the truth is $Θ (n lo g n)$ .

Verify: $R (n) = n > 0$ for all $n \geq 1$ ; no fixed $c$ makes it $\leq 0$ . ✓ Rejection is correct, not a computational slip.

Example 4 — Cell C4: stubborn residual → strengthen the hypothesis

Worked example

$T (n) = 2 T (n /2) + 1$ , prove $T (n) = O (n)$ . Forecast: the extra cost is a tiny constant $1$ , not $n$ . Does the naive $c n$ guess work, or does a small residual sabotage it?

Step 1 — Naive guess. $T (n) \leq c n$ . Step 2–3 — Substitute. $T (n) \leq 2 (c \frac{n}{2}) + 1 = c n + 1.$ Step 4 — Residual. $R (n) = 1 > 0$ . A constant residual, but still positive — cannot be absorbed by tuning $c$ (the $+ 1$ has no $c$ in it). Why this step? Even a lowly $+ 1$ breaks the strict $\leq c n$ ; this is the "stubborn lower-order term".

Step 5 — Strengthen the hypothesis. Guess the stronger $T (n) \leq c n - d$ for a constant $d > 0$ . Why this step (feels backwards but is right)? A stronger IH gives you more to assume for the subproblems, hence more slack to spend on the residual.

Step 6 — Re-substitute with the stronger guess. $T (n) \leq 2 (c \frac{n}{2} - d) + 1 = c n - 2 d + 1.$ We want this $\leq c n - d$ , i.e. $c n - 2 d + 1 \leq c n - d ⟺ - 2 d + 1 \leq - d ⟺ 1 \leq d .$ So choose $d = 1$ . Why this step? The extra $- d$ (times two subproblems, giving $- 2 d$ ) overpays the residual; the arithmetic pins $d \geq 1$ .

Step 7 — Base case. At $n = 1$ , need $T (1) \leq c \cdot 1 - 1 = c - 1$ , so pick $c \geq T (1) + 1$ . Why this step? The subtracted $d$ makes the base case slightly harder — always re-check it after strengthening.

Verify: with $d = 1$ : $c n - 2 (1) + 1 = c n - 1 = c n - d$ . ✓ The stronger bound $T (n) \leq c n - 1$ holds, and since $c n - 1 \leq c n$ , we get $T (n) = O (n)$ . (True answer is indeed $Θ (n)$ — a full binary tree of $n$ leaves.)

Example 5 — Cell C5: unequal splits (two different sizes)

Worked example

$T (n) = T (n /3) + T (2 n /3) + n$ , prove $T (n) = O (n lo g n)$ . Forecast: the split is lopsided — a third and two-thirds. The subtree costs are unequal. Do you expect the same $n lo g n$ as the balanced case?

This example is drawn in the figure below.

Step 1 — Guess. $T (n) \leq c n lo g_{2} n$ . Why this step? Total work per level is still $\approx n$ ; unequal splits usually keep the $n lo g n$ shape (see the Recursion Tree Method).

Step 2 — Assume. $T (n /3) \leq c \frac{n}{3} lo g_{2} \frac{n}{3}$ and $T (2 n /3) \leq c \frac{2 n}{3} lo g_{2} \frac{2 n}{3}$ . Why this step? Both $\frac{n}{3} < n$ and $\frac{2 n}{3} < n$ , so the IH applies to each piece.

Step 3 — Substitute. $T (n) \leq c \frac{n}{3} lo g_{2} \frac{n}{3} + c \frac{2 n}{3} lo g_{2} \frac{2 n}{3} + n .$ Why this step? Plug both bounds in.

Step 4 — Massage. Split the logs: $lo g_{2} \frac{n}{3} = lo g_{2} n - lo g_{2} 3$ and $lo g_{2} \frac{2 n}{3} = lo g_{2} n - lo g_{2} \frac{3}{2}$ . $= c n lo g_{2} n - c n [\frac{1}{3} lo g_{2} 3 + \frac{2}{3} lo g_{2} \frac{3}{2}] + n .$ Why this step? We want $c n lo g_{2} n$ isolated so the bracket becomes the residual coefficient.

Step 5 — Residual. Let $K = \frac{1}{3} lo g_{2} 3 + \frac{2}{3} lo g_{2} \frac{3}{2} \approx \frac{1}{3} (1.585) + \frac{2}{3} (0.585) \approx 0.528 + 0.390 = 0.918.$ $R (n) = - c n K + n = n (1 - cK) .$ Why this step? $K$ (about $0.918$ ) is exactly the "entropy" of the $\frac{1}{3}, \frac{2}{3}$ split — it measures how much the log shrinks.

Step 6 — Absorb. Need $1 - cK \leq 0$ , i.e. $c \geq \frac{1}{K} \approx \frac{1}{0.918} \approx 1.089$ . Choose $c = 2$ comfortably. Why this step? One fixed $c$ handles both subtrees at once.

Verify: $K \approx 0.918$ , and with $c = 2$ : $1 - 2 (0.918) = 1 - 1.836 = - 0.836 \leq 0$ . ✓ Residual non-positive → $T (n) = O (n lo g n)$ .

Example 6 — Cell C6: subtractive recurrence $T (n - 1)$

Worked example

$T (n) = T (n - 1) + n$ , prove $T (n) = O (n^{2})$ . Forecast: the argument shrinks by subtracting 1, not dividing. Over how many levels does the recursion run, and what does that do to the total?

Step 1 — Guess. $T (n) \leq c n^{2}$ . Why this step? $n$ levels, each adding up to $\sim n$ work, smells quadratic (it is the arithmetic series $1 + 2 + \dots + n$ ).

Step 2 — Assume. $T (n - 1) \leq c (n - 1)^{2}$ . Why this step? $n - 1 < n$ ; the subtractive step is still "smaller", so the IH applies.

Step 3 — Substitute. $T (n) \leq c (n - 1)^{2} + n .$ Step 4 — Massage. $(n - 1)^{2} = n^{2} - 2 n + 1$ , so $= c n^{2} - 2 c n + c + n = goal c n^{2} + R (n) (- 2 c n + c + n) .$ Step 5 — Absorb. $R (n) = - 2 c n + n + c = n (1 - 2 c) + c$ . For large $n$ the $n (1 - 2 c)$ term dominates, so we need $1 - 2 c < 0$ , i.e. $c > \frac{1}{2}$ . Take $c = 1$ : then $R (n) = n (1 - 2) + 1 = - n + 1 \leq 0$ for all $n \geq 1$ . Why this step? A single $c = 1$ kills the residual for every $n \geq 1$ — no accumulation.

Step 6 — Base case. $T (1) \leq c \cdot 1^{2} = 1$ . Pick $c = max (1, T (1))$ .

Verify: with $c = 1$ , at say $n = 5$ : bound is $c n^{2} = 25$ ; $R (5) = - 5 + 1 = - 4 \leq 0$ . ✓ The exact solution $T (n) = \frac{n ( n + 1 )}{2} = 15$ for $n = 5$ (if $T (1) = 1$ ) is indeed $\leq 25$ . ✓ So $T (n) = O (n^{2})$ (tight $Θ (n^{2})$ ).

Example 7 — Cell C7: change of variables (weird argument)

Worked example

$T (n) = 2 T (n) + lo g_{2} n$ , prove $T (n) = O (lo g n lo g lo g n)$ . Forecast: the subproblem size is $n$ , not $n / b$ . Direct substitution is ugly. The trick: rename the variable so the recurrence becomes familiar.

Step 1 — Change variables. Let $m = lo g_{2} n$ , so $n = 2^{m}$ and $n = 2^{m /2}$ . Define $S (m) = T (2^{m}) = T (n)$ . Why this step? Taking $lo g$ turns $n \mapsto m /2$ : a division recurrence, which we know how to attack. This is the standard Divide and Conquer variable swap.

Step 2 — Rewrite. Since $T (n) = T (2^{m /2}) = S (m /2)$ and $lo g_{2} n = m$ : $S (m) = 2 S (m /2) + m .$ Why this step? This is exactly Example 1-style $2 S (m /2) + m$ , whose answer is $O (m lo g m)$ .

Step 3 — Solve the friendly form. By the argument of the parent's Worked Example 1, $S (m) = O (m lo g_{2} m)$ . Why this step? We already proved this shape; reuse it.

Step 4 — Change back. Substitute $m = lo g_{2} n$ : $T (n) = S (m) = O (m lo g_{2} m) = O (lo g_{2} n \cdot lo g_{2} lo g_{2} n) .$ Why this step? Undo the rename to express the bound in the original variable $n$ .

Verify: sanity-check magnitudes at $n = 2^{16} = 65536$ : $m = 16$ , $S (16) \approx m lo g_{2} m = 16 \cdot 4 = 64$ ; and $lo g_{2} n \cdot lo g_{2} lo g_{2} n = 16 \cdot lo g_{2} 16 = 16 \cdot 4 = 64$ . ✓ Same number both ways — the change of variables is consistent.

Example 8 — Cell C8: the base-case / degenerate pitfall

Worked example For

$T (n) = 2 T (n /2) + n$ with claim $T (n) \leq c n lo g_{2} n$ , show why $n_{0} = 1$ fails but $n_{0} = 2$ works. Forecast: the inductive step is fine (Example 1 proved it). The danger is purely at the floor. Predict what $c n lo g_{2} n$ equals at $n = 1$ .

Step 1 — Evaluate the bound at $n = 1$ . $c n lo g_{2} n = c \cdot 1 \cdot lo g_{2} 1 = c \cdot 1 \cdot 0 = 0.$ Why this step? $lo g_{2} 1 = 0$ , so the entire bound collapses to $0$ .

Step 2 — Compare with $T (1)$ . $T (1)$ is a positive constant (some real work). We would need $T (1) \leq 0$ — impossible. Why this step? This is Mistake B: a false base case that no $c$ can rescue, because $c \cdot 0 = 0$ regardless of $c$ .

Step 3 — Shift the base to $n_{0} = 2$ . Now $c n lo g_{2} n = c \cdot 2 \cdot lo g_{2} 2 = 2 c$ , which is positive and can be made $\geq T (2)$ by choosing $c \geq \frac{T ( 2 )}{2}$ . Why this step? At $n = 2$ the log is $1 \neq = 0$ , so the bound is genuinely positive and groundable.

Step 4 — Coverage of the gap. The recurrence's recursion never needs $n = 1$ if we treat all $n \in {2, 3}$ as base cases directly; the inductive step only calls $n /2 \geq 1$ , and for $n \geq 4$ , $n /2 \geq 2 = n_{0}$ . So the induction is self-contained above $n_{0} = 2$ . Why this step? We must ensure every recursive call lands on a proven value — no dangling $n < n_{0}$ .

Verify: at $n = 1$ , $c \cdot 1 \cdot lo g_{2} 1 = 0$ for every $c$ ; at $n = 2$ , $c \cdot 2 \cdot lo g_{2} 2 = 2 c > 0$ . ✓ The floor must be $\geq 2$ .

Example 9 — Cell C9: a real-world word problem

Worked example A file-sync robot deduplicates

$n$ files. To dedup a batch it splits it into two halves, dedups each half recursively, then does a linear merge-scan costing $n$ comparisons. How long does deduping $n$ files take? Give a Big-Θ. Forecast: describe the recurrence in words first, then guess the growth before computing.

Step 1 — Translate the story to a recurrence. "Split into two halves" → two subproblems of size $n /2$ . "Linear merge-scan costing $n$ " → additive $n$ . So $T (n) = 2 T (n /2) + n .$ Why this step? Word problems are recurrences in disguise; naming $a = 2$ , $b = 2$ , $h (n) = n$ pins the shape.

Step 2 — Guess. $T (n) \leq c n lo g_{2} n$ (this is literally Merge Sort Analysis). Why this step? Balanced halving + linear merge is the canonical $n lo g n$ pattern.

Step 3 — Prove (upper). Identical to Example 1: substitute, use $lo g_{2} \frac{n}{2} = lo g_{2} n - 1$ , residual $- (c - 1) n \leq 0$ for $c \geq 1$ . ✓

Step 4 — Prove (lower). Identical to Example 2: $T (n) \geq c n lo g_{2} n$ with $c \leq 1$ . ✓

Step 5 — Combine. Upper $O (n lo g n)$ and lower $Ω (n lo g n)$ give $T (n) = Θ (n lo g n)$ . Why this step? Both bounds meeting is the definition of $Θ$ (see Big-O Big-Omega Big-Theta).

Verify (with units & numbers): for $n = 1024 = 2^{10}$ files, the model predicts $\approx n lo g_{2} n = 1024 \times 10 = 10240$ comparison-operations. Doubling to $n = 2048$ gives $2048 \times 11 = 22528 \approx 2.2 \times$ the previous — slightly more than double, the tell-tale signature of $n lo g n$ (units: comparisons). ✓

Example 10 — Cell C10: exam twist with ceilings

Worked example

$T (n) = 2 T (⌈ n /2 ⌉) + n$ , prove $T (n) = O (n lo g n)$ despite the ceiling. Forecast: the $⌈ \cdot ⌉$ makes the subproblem slightly larger than $n /2$ . Does that extra fraction break the proof?

Step 1 — Bound the ceiling. $⌈ n /2 ⌉ \leq \frac{n}{2} + \frac{1}{2} \leq \frac{3 n}{4}$ for $n \geq 2$ (since $\frac{n}{2} + \frac{1}{2} \leq \frac{3 n}{4} ⟺ \frac{1}{2} \leq \frac{n}{4} ⟺ n \geq 2$ ). Why this step? We replace the awkward ceiling by a clean fraction we can substitute. Weakening the argument bound is safe for an $O$ proof as long as it stays $< n$ .

Step 2 — Strengthen the hypothesis. Guess $T (n) \leq c n lo g_{2} n - d n$ (subtract a lower-order term to soak up the ceiling slack). Why this step?* Ceilings leave a stubborn $+ constant$ -ish residual (Mistake C territory), so we pre-arm with $- d n$ (Example 4's trick).

Step 3 — Substitute. Using $⌈ n /2 ⌉ \leq n /2$ inside the log's argument approximation (a full rigorous treatment keeps $⌈ \cdot ⌉$ ; here we use the standard clean form): $T (n) \leq 2 (c \frac{n}{2} lo g_{2} \frac{n}{2} - d \frac{n}{2}) + n = c n (lo g_{2} n - 1) - d n + n .$ Step 4 — Massage & residual. $= c n lo g_{2} n - c n - d n + n = (c n lo g_{2} n - d n) + R (n) (- c n + n) .$ So $R (n) = n (1 - c)$ . Step 5 — Absorb. Need $1 - c \leq 0$ , i.e. $c \geq 1$ . The extra $- d n$ carries through unchanged, matching the strengthened target $c n lo g_{2} n - d n$ ; any $d \geq 0$ works for the step, and $d$ is fixed by the base case. Why this step? The ceiling's slack was pre-absorbed by the $- d n$ buffer, so a fixed $c \geq 1$ still closes the step.

Step 6 — Base case. At $n_{0} = 2$ : target $c \cdot 2 \cdot 1 - 2 d = 2 c - 2 d$ ; choose $c$ large and $d$ small so $T (2) \leq 2 c - 2 d$ .

Verify: at $c = 1$ , $R (n) = n (1 - 1) = 0 \leq 0$ for all $n$ . ✓ And the ceiling bound $⌈ n /2 ⌉ \leq \frac{3 n}{4}$ at $n = 2$ : $⌈ 1 ⌉ = 1 \leq \frac{6}{4} = 1.5$ . ✓ So $T (n) = O (n lo g n)$ , ceiling and all.

Parent: Substitution method — the G-A-S-A-B engine these examples exercise.
Master Theorem — cross-checks Examples 1, 2, 9 in one line.
Recursion Tree Method — where the guesses here come from.
Mathematical Induction — the logic every example rides on.
Divide and Conquer — source of Examples 1, 2, 5, 9, 10; the change-of-variables in 7.
Big-O Big-Omega Big-Theta — the $O$ / $Ω$ / $Θ$ distinctions in Examples 2 and 9.
Merge Sort Analysis — Example 9 in full.

Worked examples — Substitution method for recurrences

The scenario matrix

Example 1 — Cell C1: clean absorb, upper bound

Example 2 — Cell C2: lower bound $Ω$ (the inequality flips)

Example 3 — Cell C3: the guess is too tight (a correct rejection)

Example 4 — Cell C4: stubborn residual → strengthen the hypothesis

Example 5 — Cell C5: unequal splits (two different sizes)

Example 6 — Cell C6: subtractive recurrence $T (n - 1)$

Example 7 — Cell C7: change of variables (weird argument)

Example 8 — Cell C8: the base-case / degenerate pitfall

Example 9 — Cell C9: a real-world word problem

Example 10 — Cell C10: exam twist with ceilings

Matrix check-off

Active Recall

Connections

Concept Map