Substitution method for recurrences — Hinglish notes

3.1.8 · Coding › Complexity Analysis

Yeh Hai Kya?

ASAL MEIN HUM KYA KAR RAHE HAIN: ek candidate bound $f (n)$ chunna aur prove karna ki inductive invariant " $T (k) \leq c f (k)$ for all $k < n$ " se " $T (n) \leq c f (n)$ " force hota hai.

KAISE: recipe (first principles se derivation)

Hum formula kabhi seedha nahi dalunga. Yeh raha engine, step by step.

Maano $T (n) = a T (n / b) + h (n)$ .

Guess karo $T (n) \leq c f (n)$ — ise inductive hypothesis (IH) kaho.
Maano IH sab chhote values ke liye sahi hai, khaaskar $n / b$ ke liye: $T (n / b) \leq c f (n / b) .$ Yeh step kyun? Induction hume allow karta hai ki $n$ se chhote inputs ke liye claim assume karo; $n / b < n$ qualify karta hai.
Substitute karo recurrence mein: $T (n) = a T (n / b) + h (n) \leq a c f (n / b) + h (n) .$ Yeh step kyun? $T (n / b)$ ko uske (assumed) upper bound se replace karna right side ko sirf badhata ya same rakhta hai — upper bound ke liye yeh legal hai.
Massage karo right side ko tab tak jab tak woh $\leq c f (n)$ na ho jaaye. Baaki bache terms ko absorb karna hoga. Agar tum $c$ aisa chun sako ki residual $\leq 0$ ho jaaye, tum jeet gaye.
Base case: chhote $n$ check karo (jaise $n = 1$ ) taaki induction grounded rahe.

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

Worked Example 2 — subtle constant trap

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

Common mistake Classic errors ko steel-man karna

Mistake A — "Maine prove kiya $T (n) \leq (c + 1) n$ , toh $T (n) = O (n)$ ." Kyun sahi lagta hai: $(c + 1) n$ ab bhi linear hai, "bas ek bada constant." Kharabi: induction maangta hai ki wahi $c$ reproduce karo jo tumne assume kiya tha. Har level par ek bada constant $lo g n$ levels mein accumulate hota hai → woh actually $Θ (n lo g n)$ hai. Fix: residual ek fixed $c$ ke saath $\leq 0$ hona chahiye, ya guess strengthen karo.

Mistake B — base case bhool jaana. Tum induction se kuch bhi "prove" kar sakte ho agar base case ignore karo. Fix: hamesha verify karo $T (n_{0}) \leq c f (n_{0})$ , aur $n_{0}$ wahan chuno jahan $f$ positive ho ( $lo g 1 = 0$ se bachao).

Mistake C — induction ke andar sloppy asymptotics. $T (n) \leq c f (n /2) + O (n) \leq c f (n)$ likhne se constant chhup jaata hai. $O (n)$ exactly woh term ho sakti hai jo absorb nahi ho sakti. Fix: constant ko explicitly carry karo bilkul end tak.

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho ek magic box hai jo, ek badi question ka jawab dene ke liye, khud ke do chhote copies se poochh ta hai aur thoda apna kaam bhi karta hai. Tum jaanna chahte ho poori cheez kitna time leti hai. Tum ek smart guess karte ho ("mujhe lagta hai isme $n lo g n$ seconds lagenge"). Phir ek game khelate ho: maano chhote boxes already tumhari guess maante hain, use plug in karo, aur check karo ki bada box abhi bhi ise maanta hai ya nahi. Agar baaki kaam gayab ho jaaye (zero ya negative ho jaaye), tumhara guess sahi tha! Agar koi zidd piece nahi jaata, tumhara guess galat tha aur tum ek bada try karte ho. Tum sabse chhota box hath se bhi check karte ho taaki "maano" ka poora chain solid ground par khara rahe.

Active Recall

Substitution method ke do steps kya hain?

(1) Solution ki form guess karo; (2) induction se prove karo, constants dhundho.

Method ka naam "substitution" kyun hai?

Kyunki hum inductive hypothesis (chhote inputs ke liye guess) ko wapas recurrence mein substitute karte hain bound verify karne ke liye.

T (n) \leq c f (n)

prove karte waqt residual/leftover terms ka kya hona chahiye?

Woh ek akele fixed constant

c

ke liye

\leq 0

honni chahiye (yaani poori tarah absorb ho jaayein).

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

ke liye tight bound kya hai aur

O (n)

kyun nahi hai?

Θ (n lo g n)

;

O (n)

assume karne se

(c + 1) n

milta hai, extra

+ n

jo koi bhi fixed

c

absorb nahi kar sakta.

Inductive step ke dauran constant

c

c + 1

kyun nahi badh sakta?

Induction ko WAHI

c

reproduce karna hota hai; per-level growth

lo g n

levels mein accumulate ho jaati hai aur bound bigad jaati hai.

"Strengthen the hypothesis" trick kya hai?

Guess karo

T (n) \leq c f (n) - d

(ek lower-order term subtract karo) taaki slack mile jo zidd residuals absorb kare.

Base case check karna kyun zaroori hai?

Induction ko ground kiye bina koi bhi galat claim "prove" ki ja sakti hai; saath hi yeh chhote

n

ke liye

c

fix karta hai.

n lo g n

bound ke liye

n_{0} = 1

ki jagah

n_{0} = 2

kyun chunte hain?

lo g 1 = 0

c n lo g n = 0

ho jaata hai

n = 1

par, jo positive

T (1)

ko bound nahi kar sakta.

Connections

Master Theorem — $T (n) = a T (n / b) + f (n)$ ka shortcut; substitution ise scratch se prove karta hai.
Recursion Tree Method — tumhe woh guess deta hai jo substitution phir verify karta hai.
Mathematical Induction — andar ka logical engine.
Divide and Conquer — yahan se yeh recurrences aati hain.
Big-O Big-Omega Big-Theta — woh bounds jo hum prove kar rahe hain.
Merge Sort Analysis — canonical $2 T (n /2) + n$ example.