Substitution method for recurrences

What is it?

WHAT we are really doing: picking a candidate bound $f(n)$ and proving the inductive invariant " $T(k) \le c\,f(k)$ for all $k < n$ " forces " $T(n) \le c\,f(n)$ ".

HOW: the recipe (derivation from first principles)

We never dump a formula. Here is the engine, step by step.

Suppose $T(n) = a\,T(n/b) + h(n)$ .

Guess $T(n) \le c\,f(n)$ — call this the inductive hypothesis (IH).
Assume IH holds for all smaller values, in particular for $n/b$ : $T(n/b) \le c\,f(n/b).$ Why this step? Induction lets us assume the claim for inputs smaller than $n$ ; $n/b < n$ qualifies.
Substitute into the recurrence: $T(n) = a\,T(n/b) + h(n) \le a\,c\,f(n/b) + h(n).$ Why this step? Replacing $T(n/b)$ by its (assumed) upper bound only increases or preserves the right side — legal for an upper bound.
Massage the right side until it is $\le c\,f(n)$ . The leftover terms must be absorbed. If you can choose $c$ so the residual is $\le 0$ , you win.
Base case: check small $n$ (e.g. $n=1$ ) so the induction is grounded.

Worked Example 1 — $T(n) = 2T(n/2) + n$

Worked example Prove

$T(n) = O(n\log n)$ Guess: $T(n) \le c\,n\log n$ .

Step (assume): assume $T(n/2) \le c\,\tfrac{n}{2}\log\tfrac{n}{2}$ . Why? $n/2 < n$ , so IH applies.

Step (substitute): $T(n) \le 2\Big(c\,\tfrac{n}{2}\log\tfrac{n}{2}\Big) + n = c\,n\log\tfrac{n}{2} + n.$ Why? Plugged the bound into $2T(n/2)+n$ .

Step (massage): use $\log\tfrac{n}{2} = \log n - 1$ : $= c\,n\log n - c\,n + n = c\,n\log n - (c-1)n.$ Why? Splitting the log exposes the residual $-(c-1)n$ .

Step (absorb): if $c \ge 1$ , then $-(c-1)n \le 0$ , so $T(n) \le c\,n\log n. \quad\checkmark$ Why? The residual is non-positive, so it can only help the inequality.

Base case: $T(2)=$ some constant; pick $c$ large enough that $T(2)\le c\cdot2\log2$ . (We start at $n_0=2$ , not $1$ , because $\log 1 = 0$ would break it.)

Worked Example 2 — the subtle constant trap

Worked Example 3 — the subtract-a-lower-order-term trick

Worked example

$T(n) = T(n/2) + T(n/4) + n$ , prove $T(n)=O(n)$ Naive guess $T(n)\le c n$ fails: $T(n) \le c\tfrac{n}{2} + c\tfrac{n}{4} + n = \tfrac{3}{4}cn + n.$ We need $\tfrac34 cn + n \le cn$ , i.e. $n \le \tfrac14 cn$ , i.e. $c \ge 4$ . Actually this works! Choose $c\ge 4$ .

But many recurrences leave a stubborn lower-order residual. The cure is to strengthen the hypothesis: guess $T(n) \le c n - d$ (subtract a constant). The extra $-d$ gives you slack to absorb leftovers. Why this feels backwards but is right: a stronger IH gives you more to assume in the inductive step — counterintuitively making the proof easier.

Common mistake Steel-manning the classic errors

Mistake A — "I proved $T(n)\le (c+1)n$ , so $T(n)=O(n)$ ." Why it feels right: $(c+1)n$ is still linear, "just a bigger constant." The flaw: induction requires you to reproduce the same $c$ you assumed. A growing constant per level means it accumulates over $\log n$ levels → it's really $\Theta(n\log n)$ . Fix: the residual must be $\le 0$ with a fixed $c$ , or strengthen the guess.

Mistake B — forgetting the base case. You can "prove" anything by induction if the base case is ignored. Fix: always verify $T(n_0)\le c\,f(n_0)$ , and pick $n_0$ where $f$ is positive (avoid $\log 1 = 0$ ).

Mistake C — sloppy asymptotics inside induction. Writing $T(n)\le cf(n/2) + O(n) \le cf(n)$ hides the constant. The $O(n)$ might be exactly the term that can't be absorbed. Fix: carry the constant explicitly until the very end.

Recall Feynman: explain to a 12-year-old

Imagine a magic box that, to answer a big question, asks two smaller copies of itself and adds a little work of its own. You want to know how long the whole thing takes. You make a smart guess ("I bet it takes about $n\log n$ seconds"). Then you play a game: pretend the smaller boxes already obey your guess, plug that in, and check whether the big box still obeys it. If the leftover work disappears (becomes zero or negative), your guess was right! If a stubborn piece won't go away, your guess was wrong and you try a bigger one. You also check the tiniest box by hand so the whole chain of "pretends" stands on solid ground.

Active Recall

What are the two steps of the substitution method?

(1) Guess the form of the solution; (2) prove it by induction, finding the constants.

Why is the method named "substitution"?

You substitute the inductive hypothesis (the guess for smaller inputs) back into the recurrence to verify the bound.

In proving

T(n)\le c\,f(n)

, what must happen to the residual/leftover terms?

They must be

\le 0

for a single fixed constant

c

(i.e. fully absorbed).

For

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

, what is the tight bound and why isn't it

O(n)

\Theta(n\log n)

; assuming

O(n)

gives

(c+1)n

, an extra

+n

that no fixed

c

can absorb.

Why can't the constant grow from

c

c+1

during the inductive step?

Induction must reproduce the SAME

c

; a per-level growth accumulates over the

\log n

levels, blowing up the bound.

What is the "strengthen the hypothesis" trick?

Guess

T(n)\le c\,f(n)-d

(subtract a lower-order term) to gain slack that absorbs stubborn residuals.

Why must you check a base case?

Without grounding the induction, any false claim could be "proved"; also it fixes

c

for small

n

Why pick

n_0=2

rather than

1

for an

n\log n

bound?

\log 1 = 0

makes

c\,n\log n = 0

n=1

, which can't bound a positive

T(1)

Connections

Master Theorem — a shortcut for $T(n)=aT(n/b)+f(n)$ ; substitution proves it from scratch.
Recursion Tree Method — gives you the guess that substitution then verifies.
Mathematical Induction — the logical engine underneath.
Divide and Conquer — where these recurrences come from.
Big-O Big-Omega Big-Theta — the bounds we are proving.
Merge Sort Analysis — canonical $2T(n/2)+n$ example.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Substitution method ka idea simple hai: recurrence (jaise $T(n)=2T(n/2)+n$ ) apne answer ko apne andar chhupa ke rakhta hai. Hum pehle ek smart guess maarte hain — "bhai, ye toh $O(n\log n)$ lag raha hai" — aur phir induction se prove karte hain. Isko "substitution" isliye kehte hain kyunki hum apna guess (smaller input ke liye) wapas recurrence mein substitute karke check karte hain ki inequality survive karti hai ya nahi.

Recipe yaad rakho — G-A-S-A-B: Guess karo, smaller $n$ ke liye Assume karo, recurrence mein Substitute karo, jo leftover bachta hai usko Absorb karo (woh $\le 0$ hona chahiye SAME constant $c$ ke saath), aur Base case check karo. Agar leftover term ( $-(c-1)n$ wala) negative ho gaya, matlab guess sahi hai.

Sabse bada trap: agar tumhe $(c+1)n$ mila aur tum khush ho gaye ki "linear hi toh hai", toh galat! Induction mein wahi $c$ wapas aana chahiye, badhna nahi chahiye. Constant har level pe badhta jaaye toh $\log n$ levels mil ke pura $n\log n$ ban jaata hai. Isiliye $T(n)=2T(n/2)+n$ ka actual answer $\Theta(n\log n)$ hai, $O(n)$ nahi.

Aur ek pro-tip: kabhi-kabhi seedha guess fail hota hai chhote se leftover ke wajah se. Tab hypothesis ko strong karo — $T(n)\le cn - d$ guess karo. Ulta lagta hai, par stronger assumption se inductive step mein zyada cheez maan-ne ko milti hai, jisse proof aasaan ho jaata hai. Base case kabhi mat bhoolna, aur $n\log n$ ke liye $n_0=2$ se shuru karo kyunki $\log 1=0$ hota hai.

What is it?

HOW: the recipe (derivation from first principles)

Worked Example 1 — $T(n) = 2T(n/2) + n$

Worked Example 2 — the subtle constant trap

Worked Example 3 — the subtract-a-lower-order-term trick

Active Recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Complexity Analysis

Connections