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

3.7.2 · D3 · Coding › Algorithm Paradigms › Divide and conquer — template, correctness, recurrence

Yeh page ek drill hai. Parent note ne machinery banayi thi — template, recurrence $T (n) = a T (n / b) + f (n)$ , aur Master Theorem. Yahan hum us machinery par har tarah ka input daalte hain aur answer nikalte hain, taaki jab exam ya koi real problem tumhe ek recurrence de, tum uski shape pehle se dekh chuke ho.

Shuru karne se pehle, ek reminder ki har letter ka kya matlab hai, kyunki hum ise re-derive nahi karenge — hum ise har baar use karenge:

Recall Woh numbers jo tum hamesha pehle padhte ho

Question ::: $T (n) = a T (n / b) + f (n)$ mein $a$ , $b$ , $f$ kya hain? $a$ ::: kitne subproblems har call spawn karta hai $b$ ::: woh factor jisse input shrink hota hai (size $n \to n / b$ ho jaati hai) $f (n)$ ::: non-recursive work — divide cost plus combine cost $c_{crit}$ ::: derived watershed exponent $lo g_{b} a$ , yaani leaves ki cost $n^{l o g_{b} a}$ ( $a, b$ se compute hota hai, read off nahi)

Poora game yeh hai: $c_{crit} = lo g_{b} a$ compute karo, phir $f (n)$ ko $n^{c_{crit}}$ se compare karo. Teen outcomes possible hain — $f$ chhota, $f$ barabar, $f$ bada — aur kuch degenerate recurrences bhi hain jahan yeh comparison apply hi nahi hoti. Yahi hamara matrix hai.

The scenario matrix

Har divide-and-conquer recurrence jo tum miloge, in cells mein se ek mein fit hogi. Columns hain $f$ watershed $n^{l o g_{b} a}$ ke relative kaise hai; rows hain special / degenerate inputs jo naive routine ko tod dete hain.

Cell	Ise yeh cell kya banata hai	Example jo hum solve karte hain
A — Balanced (Case 2)	$f (n) = Θ (n^{l o g_{b} a})$ : divide-cost leaf-cost se match karta hai	Ex 1 (Mergesort), Ex 8 (word problem)
B — Leaf-heavy (Case 1)	$f (n)$ $n^{l o g_{b} a}$ se polynomially chhota hai	Ex 2 (Karatsuba)
C — Root-heavy (Case 3)	$f (n)$ polynomially bada hai, plus regularity hold karta hai	Ex 3
D — Single subproblem ( $a = 1$ )	tree ek chain hai, $c_{crit} = 0$	Ex 4 (Binary Search)
E — Uneven / degenerate split	subproblem sizes differ karte hain, ya ek size $0$ hai; shrink constant factor nahi hai ( $b \to 1$ ), toh floors/ceilings ko wave away nahi kiya ja sakta	Ex 5 (bad Quicksort pivot)
F — Basic Master Theorem fails	$f$ sirf ek log factor watershed se off hai — extended rule ya tree chahiye	Ex 6
G — Regularity fails	$f$ root-heavy lagta hai lekin $a f (n / b) \neq \leq k f (n)$	Ex 7
H — Exam twist	$n$ shrink / disguised recurrence	Ex 8 (word problem), Ex 9

Ab hum har cell ko hit karte hain.

Cell A — Balanced (Master Theorem Case 2)

Worked example Ex 1 — Mergesort, the archetype

$T (n) = 2 T (n /2) + Θ (n)$ solve karo.

Forecast: padhne se pehle growth guess karo. Do half-size sorts plus ek linear merge — $n^{2}$ se fast? $n$ se slow?

$a, b, f$ read off karo. Yahan $a = 2$ (do halves), $b = 2$ (har ek $n /2$ hai), $f (n) = Θ (n)$ . Yeh step kyun? Baad mein sab kuch ek comparison hai, aur jab tak yeh teen numbers nahi hain, compare nahi kar sakte.
Watershed compute karo $c_{crit} = lo g_{b} a = lo g_{2} 2 = 1$ , toh leaf cost $n^{1} = n$ hai. Yeh step kyun? $n^{c_{crit}}$ woh single yardstick hai jispe hum $f (n)$ ko hold karte hain.
Compare karo. $f (n) = Θ (n) = Θ (n^{1}) = Θ (n^{c_{crit}})$ — bilkul tie. Yahi Case 2 ki definition hai. Yeh step kyun? Tie ka matlab hai ki recursion tree ka koi bhi level dominate nahi karta; har level $Θ (n)$ same work karta hai.
Case 2 apply karo: $T (n) = Θ (n^{c_{crit}} lo g n) = Θ (n lo g n)$ . Yeh step kyun? $lo g_{2} n$ levels hain (neeche figure dekho) aur har ek $Θ (n)$ cost karta hai; equal work $\times$ number of levels $=$ multiply.

Verify karo: levels directly count karo. Depth $i$ par $2^{i}$ nodes hain har ek size $n / 2^{i}$ ka, toh level work $= 2^{i} \cdot (n / 2^{i}) = n$ . Size $1$ tak levels ki number: $lo g_{2} n$ . Total $= n lo g_{2} n$ . ✓ Match karta hai. Dekho Mergesort aur Recurrence Relations.

Figure — Divide and conquer — template, correctness, recurrence

Figure padhne ka tarika: har row recursion ka ek level hai. Black dots subproblems hain; right par red label unka total work dikhata hai. Notice karo punchline — haalaanki dots har level double hote hain aur half shrink hote hain, unki widths cancel ho jaati hain, toh har red label $n$ padhta hai. $lo g_{2} n$ rows hain (left par black double-arrow), aur $n$ work per row times $lo g_{2} n$ rows exactly wahi $Θ (n lo g n)$ hai jo humne compute kiya.

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

Worked example Ex 2 — Karatsuba multiplication

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

Forecast: schoolbook char ki jagah teen half-size multiplies. $n^{2}$ se neeche? Kitna?

Read off karo: $a = 3$ , $b = 2$ , $f (n) = Θ (n)$ . Yeh step kyun? Hamesha wahi pehla move — bina teen numbers ke Master-Theorem case nahi choose kar sakte, aur yahan $a = 3$ (teen products) poori novelty hai, toh pehle ise pin karo.
Watershed: $c_{crit} = lo g_{2} 3 \approx 1.585$ . Leaf cost $n^{1.585}$ . Yeh step kyun? Yahan $a \neq = b$ , toh exponent ek clean integer nahi hai — tum actually log lena padega, eyeballing nahi chalega.
Compare karo. Class $f (n) = Θ (n)$ se representative $n$ lo (class mein koi bhi function same compare karta hai). Kya $n$ , $n^{1.585}$ se chhota hai? Haan, aur polynomially bhi: $n = n^{1.585 - ε}$ with $ε \approx 0.585 > 0$ . Yeh Case 1 hai. Yeh step kyun? Case 1 ko gap ek genuine power of $n$ chahiye (sirf log factor nahi); $0.585$ ek fat polynomial gap hai, toh hum safe hain.
Case 1 apply karo: leaves sab kuch swamp kar dete hain, $T (n) = Θ (n^{l o g_{2} 3}) \approx Θ (n^{1.585})$ .

Verify karo: leaf term alone $n^{l o g_{2} 3} = n^{1.585}$ hai; summed non-recursive work ratio $a / b = 3/2 > 1$ wali geometric series hai, apne last (leaf) term se dominated — toh total $= Θ (n^{1.585})$ . Aur $1.585 < 2$ , schoolbook ko beat karta hai. ✓ Dekho Karatsuba.

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

Worked example Ex 3 — expensive combine wala divide

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

Forecast: combine step $n^{2}$ heavy hai. Kya recursion abhi bhi matter karti hai, ya top call dominate karta hai?

Read off karo: $a = 2$ , $b = 2$ , $f (n) = Θ (n^{2})$ . Yeh step kyun? Yahan ek heavy ingredient $f (n) = n^{2}$ hai — ek expensive combine — toh hum ise explicitly identify karte hain test karne se pehle ki yeh watershed ke kis taraf land karta hai.
Watershed: $c_{crit} = lo g_{2} 2 = 1$ , leaf cost $n^{1}$ . Yeh step kyun? Yardstick $n^{c_{crit}} = n^{1}$ haath mein chahiye taaki dekh sakein ki combine cost $n^{2}$ usse kitna upar hai.
Compare karo: $f (n) = n^{2}$ vs $n^{1}$ . Ab $f$ bada hai, polynomially: $n^{2} = n^{1 + ε}$ with $ε = 1 > 0$ . Candidate Case 3. Yeh step kyun? Case 3 "root dominates" case hai; claim karne se pehle confirm karna hoga ki $f$ leaves ko ek honest power of $n$ se beat karta hai, aur $ε = 1$ exactly wahi confirmation hai.
Regularity condition check karo $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) .$ Toh $k = \frac{1}{2} < 1$ . ✓ Regularity hold karta hai. Yeh step kyun? Case 3 ek promise hai ki work tree se neeche jaate hue shrink karta hai; regularity us promise ka proof hai. Skip karo aur galat ho sakte ho (dekho Ex 7).
Case 3 apply karo: $T (n) = Θ (f (n)) = Θ (n^{2})$ .

Verify karo: per-level work hai $n^{2}, \frac{n ^{2}}{2}, \frac{n ^{2}}{4}, \dots$ — ratio $\frac{1}{2}$ wali geometric series, sum $2 n^{2} = Θ (n^{2})$ , root se dominated. ✓

Figure padhne ka tarika: har bar ek recursion level par total work hai, $n^{2}$ ki units mein. Ex 1 ke flat profile ke unlike, yahan bars geometrically shrink karte hain — har ek pichle ka half hai. Depth $0$ par tall red bar root hai, aur kyunki bars itni fast girti hain, poora tower bas $2 \times$ us pehle bar ko sum karta hai. "Root dominates" yaise dikhta hai, aur isliye answer $Θ (n^{2})$ hai, sirf root ki cost.

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

Worked example Ex 4 — Binary search

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

Forecast: tum array ka aadha phenko aur kabhi wapas nahi dekhte. Kitne steps?

Read off karo: $a = 1$ , $b = 2$ , $f (n) = Θ (1)$ . Yeh step kyun? Notice $a = 1$ : har call ek recursive call karta hai, toh "tree" ek single vertical chain hai, branching tree nahi.
Watershed: $c_{crit} = lo g_{2} 1 = 0$ , leaf cost $n^{0} = 1$ . Yeh step kyun? $1$ ka $lo g$ $0$ hai — leaves ek constant cost karte hain, $n$ ka power nahi. Yahi single-subproblem recurrences ko itna cheap banata hai.
Compare karo: $f (n) = Θ (1) = Θ (n^{0}) = Θ (n^{c_{crit}})$ — tie, Case 2. Yeh step kyun? Hum $f$ ko yardstick $n^{c_{crit}} = n^{0} = 1$ se compare karte hain; dono constant hain, toh na root na leaves dominate karta hai — Case 2 ki pehchaan.
Case 2 apply karo: $T (n) = Θ (n^{0} lo g n) = Θ (lo g n)$ . Yeh step kyun? Case 2 leaf cost ko levels ki number se multiply karta hai; leaf cost $n^{0} = 1$ aur $lo g n$ levels ke saath, product exactly $Θ (lo g n)$ hai.

Verify karo: chain ki length "kitni baar $n$ ko halve kar sakte ho $1$ tak pahunchne ke liye" $= lo g_{2} n$ hai, har ek $Θ (1)$ work karta hai → $Θ (lo g n)$ . ✓ Dekho Binary Search.

Figure padhne ka tarika: $a = 1$ ki wajah se picture ek single vertical stack hai, branching tree nahi — har level par ek dot, har ek apni shrinking size ( $n, n /2, n /4, \dots$ ) aur constant $O (1)$ work ke saath labelled. Neeche red dot base case hai, size $1$ . Black double-arrow rungs count karta hai: $lo g_{2} n$ of them, har ek $O (1)$ karta hai, toh total $Θ (lo g n)$ hai.

Cell E — Uneven / degenerate split

Worked example Ex 5 — Quicksort ka worst pivot (size-

$0$ subproblem) Ek bura pivot sab kuch ek side par daal deta hai. Recurrence ban jaata hai $T (n) = T (n - 1) + T (0) + Θ (n) .$ Ise solve karo.

Forecast: split $n - 1$ aur $0$ hai — "divide" barely shrink karta hai. Kya yeh abhi bhi $n lo g n$ hai? Ya bura?

Size- $0$ term collapse karo. Hamare base-case convention se $T (0) = Θ (1)$ , toh yeh $Θ (n)$ non-recursive work mein absorb ho jaata hai: $T (n) = T (n - 1) + Θ (1) + Θ (n) = T (n - 1) + Θ (n) .$ Yeh step kyun? Size $0$ ka subproblem koi recursion nahi karta — woh bas ek constant return karta hai. Us constant ko explicitly name karna ( $T (0) = Θ (1)$ ) hi use allow karta hai $Θ (n)$ term mein drop karne ke liye, bajaaye ek mysterious second recursive call chhod ne ke.
Degeneracy spot karo. Surviving subproblem size $n - 1$ hai: shrink $n \to n - 1$ hai, i.e. $b \to 1$ . Master Theorem apply nahi hota. Yeh step kyun? $lo g_{b} a$ , $b \to 1$ hote hi blow up karta hai; poora comparison framework ek constant-factor shrink assume karta hai, jo yahan nahi hai. Yeh woh jagah bhi hai jahan page ke top se floor/ceiling rescue fail hota hai — input additive $1$ se drop hota hai, multiplicative factor se nahi.
Haath se unroll karo instead: $T (n) = Θ (n) + Θ (n - 1) + \dots + Θ (1) = Θ (\sum_{k = 1}^{n} k) .$ Yeh step kyun? Jab shortcut void ho, definition par wapas jao: ek recurrence bas apne aap ko apne aap mein substitute karne ki instruction hai. $T (n) = T (n - 1) + Θ (n)$ ko repeatedly expand karna wahi substitution hai, aur yeh har level par ek $Θ (n), Θ (n - 1), \dots$ term expose karta hai — ek sum jo hum directly evaluate kar sakte hain.
Arithmetic series sum karo: $\sum_{k = 1}^{n} k = \frac{n ( n + 1 )}{2} = Θ (n^{2})$ . Yeh step kyun? Substitutions ki chain ne ek plain arithmetic series produce ki; Gauss ka closed form $\frac{n ( n + 1 )}{2}$ use ek clean $Θ$ -class mein badalta hai.
Conclude karo $T (n) = Θ (n^{2})$ .

Verify karo: $n = 4$ ke liye: $4 + 3 + 2 + 1 = 10 = \frac{4 \cdot 5}{2}$ . ✓ Worst-case Quicksort sach mein quadratic hai — yeh cell isliye hai ki pivot choice matter karti hai.

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

Worked example Ex 6 — Case 2 aur Case 3 ke beech ki recurrence

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

Forecast: $n lo g n$ $n$ se barely upar hai. Kaunsa case? (Trick question.)

$a, b$ aur watershed read off karo: $a = 2$ , $b = 2$ , $c_{crit} = lo g_{2} 2 = 1$ , leaf cost $n^{1}$ ; aur $f (n) = Θ (n lo g n)$ . Yeh step kyun? Hamesha wahi opening move — bina $a$ , $b$ , aur derived $c_{crit}$ ke koi case choose nahi ho sakta, toh pehle pin karo aur note karo ki yahan $f$ plain $n$ se extra $lo g n$ carry karta hai.
Compare karo: $f (n) = n lo g n$ vs $n^{1}$ . Kya $f$ polynomially bada hai, i.e. $n lo g n \geq n^{1 + ε}$ for some fixed $ε > 0$ ? Nahi — $lo g n$ kisi bhi power $n^{ε}$ se slow grow karta hai. Toh $f$ sirf ek log factor se bada hai, polynomial factor se nahi. Yeh step kyun? Basic teen-case Master Theorem Cases 1 aur 3 ke liye polynomial gap demand karta hai. Log-sized gap ek aise crack mein fall karta hai jo basic version cover nahi kar sakta.
Sahi tool lo. Do clean options hain jo exactly is crack ko handle karte hain:
- Extended Master Theorem $f (n) = Θ (n^{c_{crit}} lo g^{k} n)$ for integer $k \geq 0$ ko cover karta hai, deta hai $T (n) = Θ (n^{c_{crit}} lo g^{k + 1} n)$ . Yahan $k = 1$ , toh $T (n) = Θ (n lo g^{2} n)$ turant.
- Ya recursion tree par fall back karo first-principles derivation ke liye. 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) .$ Yeh step kyun? Tree method kabhi fail nahi hoti — yeh har level ka work raw recurrence se koi case analysis ke bina compute karta hai. Hum ise (ya extended rule ko) precisely isliye reach karte hain kyunki basic teen-case version ne fire karne se mana kar diya.
Tree ko $i = 0$ se $lo g_{2} n$ tak sum karo: $\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) .$ Yeh step kyun? Inner sum $0 + 1 + \dots + lo g n$ ek arithmetic series $Θ (lo g^{2} n)$ hai — aur yeh extended-rule answer se agree karta hai, dono ko confirm karta hai.
Conclude karo $T (n) = Θ (n lo g^{2} n)$ .

Verify karo: $n = 8$ par (toh $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}$ , $n \cdot Θ (lo g^{2} n)$ se match karta hai. ✓

Cell G — Regularity fails (sirf shape se root-heavy)

Worked example Ex 7 — kyun regularity check skip nahi kar sakte

Is cell mein do recurrences contrast hain jo dono root-heavy lagte hain. Case (i) regularity pass karta hai aur cleanly solve hota hai; case (ii) fail karta hai aur dikhata hai ki check kyun matter karta hai.

Forecast: dono ka $f$ , $n^{1}$ se bahut upar hai. Zarur dono Case 3 hain?

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

Watershed: $c_{crit} = lo g_{2} 2 = 1$ , leaf cost $n^{1}$ . Yeh step kyun? Hamesha wahi yardstick; $n^{2} / lo g n$ judge karne ke liye $n^{1}$ jaanna zaruri hai.
Polynomial-gap test: kya $\frac{n ^{2}}{l o g n} \geq n^{1 + ε}$ fixed $ε > 0$ ke liye? $ε = \frac{1}{2}$ lo: chahiye $\frac{n ^{2}}{l o g n} \geq n^{1.5}$ , i.e. $n^{0.5} \geq lo g n$ — sab large $n$ ke liye sach. Toh haan, $f$ watershed se polynomially upar hai → candidate Case 3. Yeh step kyun? Case 3 pehle genuine power-of- $n$ gap demand karta hai; denominator mein $lo g$ harmless hai kyunki $n^{0.5}$ eventually use dwarf kar deta hai.
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} .$ Large $n$ ke liye, $\frac{l o g n}{2 ( l o g n - 1 )} \to \frac{1}{2} < 1$ , toh valid $k < 1$ exist karta hai. ✓ Regularity hold karta hai. Yeh step kyun? Regularity guarantee karta hai ki per-level work geometrically decay karta hai, jo exactly root ko dominate karne deta hai.
Conclude (i): Case 3 fire karta hai, $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)$ peaks par $n^{2}$ tak jaata hai, jo peaks par $Ω (n^{1.5})$ hai — yeh root-heavy lagta hai.
Regularity fail karta hai. Kyunki $cos^{2} n$ infinitely often $0$ tak dip karta hai, koi single $k < 1$ nahi hai jisse $2 f (n /2) \leq k f (n)$ sab $n$ ke liye ho: ek aise $n$ par jahan $f (n) \approx 0$ lekin $f (n /2)$ apne peak ke paas hai, inequality outright violate ho jaati hai. Yeh step kyun? Regularity wada hai "work tree se neeche jaate hue decay karta hai." Oscillating $f$ us waade ko tod deta hai, toh "root dominates" simply galat hai, aur Case 3 koi conclusion nahi deta.
Conclude (ii): Master Theorem yahan kuch nahi kehta; tum tree ya Akra–Bazzi par fall back karoge (Ex 6 ka box).

Verify karo (numeric, case (i) at $n = 16$ ): check karo $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 $n = 16$ par hold karta hai — lekin sirf isliye kyunki humne check kiya.

Cell A / H — Real-world word problem

Worked example Ex 8 — Tournament: champion dhundhna

$n = 1, 024$ players. Ek match do players ko $1$ unit of time mein compare karta hai; winner aage badhta hai. Tum ek knockout bracket organize karte ho: field ko half mein split karo, har half ka champion recursively dhundho, phir ek final match khelo. Champion crown karne mein kitna time?

Forecast: $1024$ players ka knockout — $10$ matches deep ke kareeb ya $1000$ matches total?

Recurrence ki tarah model karo. Do halves size $n /2$ ke ( $a = 2, b = 2$ ), combine = woh single final match, cost $Θ (1)$ : $T (n) = 2 T (n /2) + Θ (1) .$ Yeh step kyun? "Split, har half par recurse karo, ek merge match" divide-and-conquer template verbatim hai — story ko $a, b, f$ mein turn karna hi ek tarika hai machinery reuse karne ka.
Watershed: $c_{crit} = lo g_{2} 2 = 1$ , leaf cost $n^{1}$ . Yeh step kyun? Hume $n^{1}$ chahiye taaki dekh sakein ki cheap $Θ (1)$ combine usse neeche hai.
Compare karo: $f (n) = Θ (1) = Θ (n^{0})$ , jo $n^{1}$ se polynomially neeche hai ( $ε = 1$ ) → Case 1. Yeh step kyun? Yahan combine cheap hai lekin branching rich hai — leaves ( $n$ first-round players) dominate karte hain.
Case 1 apply karo: $T (n) = Θ (n^{1}) = Θ (n)$ . Concretely, $n$ players ke knockout ko exactly $n - 1$ matches chahiye (har match ek player ko eliminate karta hai, aur $n - 1$ ko eliminate karna hai).

Verify karo: $n = 1024 \Rightarrow n - 1 = 1023$ matches total. Bracket depth $lo g_{2} 1024 = 10$ rounds hai — lekin total work $Θ (n) = 1023$ hai, Case 1 se match karta hai, $Θ (lo g n)$ nahi. ✓

Cell H — Exam twist ( $n$ shrink)

Worked example Ex 9 — change-of-variable trick

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

Forecast: input square root se shrink karta hai, constant factor se nahi. Master Theorem $n / b$ chahta hai — yeh woh shape nahi hai. Ab kya?

Substitute karo $m = lo g_{2} n$ , i.e. $n = 2^{m}$ . Phir $n = 2^{m /2}$ , toh $T (n)$ ban jaata hai $T (2^{m /2})$ . $S (m) = T (2^{m})$ let karo: $S (m) = 2 S (m /2) + Θ (m) .$ Yeh step kyun? $n$ shrink ek constant factor nahi hai, toh koi $b$ exist nahi karta aur Master Theorem stuck ho jaata hai. Lekin $n$ $n$ ke exponent ko half karta hai. Agar hum exponent ko apna naya variable $m$ bana lein, toh ugly square root ek clean division by $2$ ban jaata hai — exactly $S (m) = 2 S (m /2) + \dots$ shape restore karta hai jiske liye theorem banaya gaya tha. Change of variable standard move hai jab bhi shrink exponent mein multiplicative ho, $n$ mein nahi.
$S (m) = 2 S (m /2) + Θ (m)$ solve karo. Yeh exactly Ex 1 (Mergesort ki shape) hai: $a = 2, b = 2, c_{crit} = 1$ , $f (m) = Θ (m)$ → Case 2 → $S (m) = Θ (m lo g m)$ . Yeh step kyun? Humne deliberately problem ko ek aise mein transform kiya jo hum pehle hi solve kar chuke hain, toh hum simply Ex 1 ko quote karte hain bajaaye tree redo karne ke.
Back substitute karo $m = lo g n$ : $T (n) = S (lo g n) = Θ (lo g n \cdot lo g lo g n) .$ Yeh step kyun? Humne $S (m) = T (2^{m})$ define kiya tha, toh $T (n) = S (lo g_{2} n)$ ; $m = lo g n$ ko $m lo g m$ mein plug karo original variable par wapas aane ke liye.

Verify karo: $n = 2^{16}$ lo, toh $m = lo g_{2} n = 16$ .

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

Dono routes $64$ dete hain, toh $T (2^{16}) = S (16)$ aur change of variable consistent hai. ✓ Closed form $T (n) = Θ (lo g n \cdot lo g lo g n)$ check out karta hai.

Recall Self-test

$T (n) = 4 T (n /2) + n^{2}$ solves to? ::: $c_{crit} = lo g_{2} 4 = 2$ , $f = n^{2}$ tie karta hai → Case 2 → $Θ (n^{2} lo g n)$ $T (n) = T (n - 1) + 1$ solves to? ::: Master-able nahi ( $b \to 1$ ); unroll karo → $Θ (n)$ Tournament $Θ (n)$ kyun deta hai $Θ (lo g n)$ nahi? ::: depth $lo g n$ hai, lekin total work (leaves) dominate karta hai → $n - 1$ matches

Related paradigms is same recurrence machinery par build karte hain: Strassen Matrix Multiplication (Karatsuba jaisi Case-1 win), Mathematical Induction (correctness engine), aur Dynamic Programming (jab subproblems overlap karte hain independent hone ki jagah, tab ise use karo).