Visual walkthrough — Divide and conquer — template, correctness, recurrence

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

Hum sab kuch zero se build karte hain. Agar aapne pehle kabhi recursion tree, logarithm, ya symbol $\Theta$ nahi dekha, tab bhi Step 1 se shuru karo — har cheez use hone se pehle earn ki jaati hai.

Step 1 — Ek recurrence asal mein kya kehti hai

KYA. Hum ek line se shuru karte hain, divide-and-conquer template ka wada: $T(n)=\underset{\begin{array}{c}\text{how many}\\ \text{copies}\end{array}}{\underbrace{a}}\underset{\begin{array}{c}\text{same}\\ \text{cost rule}\end{array}}{\underbrace{T}}\left(\underset{\begin{array}{c}\text{smaller}\\ \text{size}\end{array}}{\underbrace{\frac{n}{b}}}\right)+\underset{\begin{array}{c}\text{work here,}\\ \text{not recursion}\end{array}}{\underbrace{f(n)}}$

Seedhe shabdon mein padho: size-$n$ job ki cost barabar hai $a$ copies ki cost size-$n/b$ job ki, plus $f(n)$ — woh divide+combine kaam jo aap khud recursive calls se pehle/baad karte ho.

• $T(n)$ = size-$n$ problem mein kitne basic steps lagte hain. $T$ ek function hai: size do, time milega.
• $a$ = har call mein kitne subproblems bante hain (mergesort: 2, binary search: 1, Karatsuba: 3).
• $b$ = shrink factor — size $n$ ka input, size $n/b$ ban jaata hai.
• $f(n)$ = woh kaam jo aap bina recurse kiye karte ho: array split karna, results merge karna.

RECURRENCE KYUN? Kyunki $T$ khud apne aap ke terms mein define hai. Hum seedha answer nahi padh sakte; hume self-reference ko unfold karna hoga jab tak woh ruk na jaaye. Woh unfolding hi ek tree hai.

PICTURE. Ek box jo $a$ chhote boxes ko call karta hai, har ek apne size aur local work ke saath label hua.

Step 2 — Ek level unfold karo: tree badata hai

KYA. Har $T(n/b)$ ko uski apni definition se replace karo. Recurrence ko size $n/b$ par apply karne par milta hai: $T\left(\frac{n}{b}\right)=aT\left(\frac{n}{b^2}\right)+f\left(\frac{n}{b}\right).$ Isse $T(n)=f(n)+aT(n/b)$ mein substitute karo aur $a$ ko bracket ke andar distribute karo: $T(n)=f(n)+a[aT(\frac{n}{b^2})+f(\frac{n}{b})]=f(n)+\underset{\text{level 1 total}}{\underbrace{af(\frac{n}{b})}}+a^{2}T(\frac{n}{b^2})$

Level 1 par term by term:

• $a$ children hain ⟶ factor $a$,
• har ek $f(n/b)$ local work karta hai (uski size $n/b$ hai),
• to poora level 1 $a\cdot f(n/b)$ cost karta hai;
• aur $a\cdot a=a^2$ subproblems size $n/b^2$ ke abhi bhi wait kar rahe hain (level 2).

UNFOLD KYUN KAREIN? Self-reference $T$ abhi bhi wahan hai ($a^{2}T(n/b^2)$). Hum tab tak expand karte rahenge jab tak $T$ kisi aisi size par na pahunche jiska jawab hume free mein pata ho (base case). Har expansion ek honest, recursion-free level of work ko peel off karta hai — aur unhe hum add kar sakte hain.

PICTURE. Abhi do poore levels draw hain; level-1 boxes apne $a\cdot f(n/b)$ total ke saath lit up hain.

Step 3 — Depth $i$ par pattern

KYA. Chalte raho. Depth $i$ par (root depth $0$ hai): $\text{number of nodes}=a^i,\text{size of each}=\frac{n}{b^i},\text{local work each}=f\left(\frac{n}{b^i}\right)$ To level $i$ par total kaam hai: $\boxed{\text{level-}i\text{ cost}=a^{i}f\left(\frac{n}{b^i}\right)}$

Box padho:

• $a^i$ — har level node count ko $a$ se multiply karta hai, to $i$ levels baad $a^i$ nodes hain.
• $n/b^i$ — har level size ko $b$ se divide karta hai, to $i$ levels baad har node $n/b^i$ hold karta hai.
• $f(\cdot )$ — woh size local-work function mein plug karo.

YEH DO RACING QUANTITIES KYUN? Node count $a^i$ upar jaata hai, size $n/b^i$ niche jaati hai. Divide-and-conquer running time ki puri theory inhi donon ke beech ek tug-of-war hai. Jo jeete woh answer decide karta hai.

PICTURE. Teen levels stacked, generic level $i$ par $a^i$ / $n/b^i$ / $a^{i}f(n/b^i)$ pattern annotate kiya hua.

Step 4 — Tree kahan rukti hai: levels ginana

KYA. Recursion tab rukti hai jab kisi node ki size $1$ ho jaaye (base case). Set karo: $\frac{n}{b^i}=1⟹b^i=n⟹i={\log }_{b}n$

• $b^i=n$ — humne $b$ se total $i$ baar divide kiya aur size $1$ pahunche, to $b$ ko $i$ baar multiply karne par $n$ banana chahiye.
• ${\log }_{b}n$ — yeh logarithm ki definition hi hai: "kitni baar $b$ multiply karun taaki $n$ pahunch sakun?" Woh count tree ki height hai.

LEVELS KYUN GINEN? Total cost = saare levels ka sum. Sum karne ke liye, hume pata hona chahiye ki kitne levels hain — aur aakhri (leaf) level special hai, isliye hum use mark karte hain.

PICTURE. Poora tree root se leaves tak, height ${\log }_{b}n$ labelled, bottom row of leaves highlighted.

Step 5 — Leaves: bottom row ginana

KYA. Bottom level $i={\log }_{b}n$ hai. Leaves ki sankhya: $a^{{\log }_{b}n}=n^{{\log }_{b}a}$

Har leaf ek base case hai jo $\Theta (1)$ cost karti hai, to poori leaf row $\Theta \left(n^{{\log }_{b}a}\right)$ cost karti hai.

$a^{{\log }_{b}n}=n^{{\log }_{b}a}$ kyun? Yeh ek log identity hai, koi trick nahi: $a^{{\log }_{b}n}=(b^{{\log }_{b}a}{)}^{{\log }_{b}n}=b^{{\log }_{b}a\cdot {\log }_{b}n}=(b^{{\log }_{b}n}{)}^{{\log }_{b}a}=n^{{\log }_{b}a}$

• humne $a=b^{{\log }_{b}a}$ likha (yeh sirf ${\log }_{b}a$ ki definition hai),
• exponents multiply kiye,
• regroup karke $b^{{\log }_{b}n}=n$ expose kiya.

YEH EXPONENT KYUN NAME KAREIN? Isse $c_{\text{crit}}={\log }_{b}a$ kaho. Yeh akele leaves ka contribution hai. Yeh humara yardstick ban jaata hai: hum per-level work $f$ ko $n^{c_{\text{crit}}}$ se compare karte hain yeh dekhne ke liye ki tug-of-war mein kaun jeeta.

PICTURE. Leaf row ka zoom: $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ leaves, har ek ek chhota $\Theta (1)$ box.

Step 6 — Har level add karo: master sum

KYA. Total time = leaves + saare internal levels ka sum: $\boxed{T(n)=\Theta \left(n^{{\log }_{b}a}\right)+\sum _{i=0}^{{\log }_{b}n-1}{a}^{i}f\left(\frac{n}{b^i}\right)}$

• $\Theta (n^{{\log }_{b}a})$ — leaf row (Step 5),
• ${\sum }_{i=0}^{{\log }_{b}n-1}$ — root ($i=0$) se leaves ke theek upar tak har internal level $i$ add karo,
• $a^{i}f(n/b^i)$ — Step 3 se level-$i$ cost.

SUM KYUN, AUR WOH COLLAPSE KYUN HOTA HAI? Sum ke terms usually ek geometric series banaate hain — har term previous ka ek fixed ratio $r$ times hoti hai. $r$ ko genuinely ek constant banane ke liye, hume $f$ par mild conditions chahiye:

$r=a/b^c$ constant hone par, geometric series ek END se dominated hoti hai:

• $r<1$ (terms niche shrink karte hain) ⟶ root dominate karta hai ⟶ $T=\Theta (f(n))$.
• $r=1$ (saare terms equal) ⟶ har level same cost karti hai, ${\log }_{b}n$ of them ⟶ $T=\Theta (f(n)\log n)$.
• $r>1$ (terms niche grow karte hain) ⟶ leaves dominate karti hain ⟶ $T=\Theta (n^{{\log }_{b}a})$.

Yeh teen outcomes exactly Master Theorem ke teen cases hain — lekin ab tum kyun teen cases hain yeh dekh sakte ho: ek geometric series ke sirf teen moods hote hain.

PICTURE. Har level ke liye ek bar (bar height = us level ki cost) teen moods ke liye: shrinking bars, flat bars, growing bars.

Step 7 — Chaar real algorithms, side by side dekhe

KYA. Landmark recurrences plug karo aur bars padho. Har mood ka ek representative.

YEH CHAAR KYUN? Flat ($r=1$), degenerate $a=1$ chain, root-heavy ($r<1$), aur leaf-heavy ($r>1$) — picture ab har mood ko cover karti hai jo bars le sakte hain.

PICTURE. Chaar mini-trees apne bar-profiles ke saath: mergesort (flat), binary search (thin chain), root-dominated (top-heavy, shrinking), Karatsuba (bottom-heavy, growing).

Step 8 — Degenerate & edge cases jo picture mein cover hone chahiye

KYA. Koi bhi scenario undrawn mat chhodna. Chaar corners:

1. $a=1$ (binary search): "tree" ek single vertical chain hai — koi branching nahi. Sirf height ${\log }_{b}n$ matter karta hai. Yeh koi bug nahi; sum abhi bhi kaam karta hai, bas har level par ek node hai.
2. $b=1$ (size kabhi nahi shrinkti): tab $n/b^i=n$ hamesha ke liye — infinite recursion. Tree ka koi bottom nahi. Yeh no-progress failure hai; recurrence ka koi solution nahi kyunki algorithm kabhi terminate nahi karta. (Parent ke base-case warning se match karta hai.)
3. $n=1$ at the top: hum already ek leaf hain. $T(1)=\Theta (1)$, zero recursive calls. Step 6 ka sum empty hai; boxed formula phir bhi $\Theta (1^{{\log }_{b}a})=\Theta (1)$ return karta hai. ✓
4. Master-Theorem gap — $T(n)=2T(n/2)+n\log n$: yahan $f$ ek clean power nahi hai, to ratio $r$ constant rehne ki bajay level ke saath drift karta hai — $f$ ek log-factor upar baithti hai $n^{c_{\text{crit}}}=n^1$ se. Clean geometric nahi ⟶ Master Theorem ka koi case nahi banta. Tree abhi bhi kaam karta hai: $\log n$ levels mein se har ek $\approx n\log n$ cost karta hai, sum hoke $\Theta (n{\log }^{2}n)$ milta hai. Tree use karo, ya Recurrence Relations / Akra–Bazzi.

YEH KYUN DIKHAYEIN? Cases 1–3 woh hain jahan ek naive reader sochta hai machinery "break" ho gayi; hoti nahi — tree formula unhe absorb kar leta hai. Case 4 woh hai jahan shortcut break hota hai lekin tree survive karta hai — proof ki picture fundamental object hai, Master Theorem sirf uska clean corollary hai.

PICTURE. Chaar small panels: chain ($a=1$), bottomless tree ($b=1$), single leaf ($n=1$), aur $n\log n$ near-miss apne slightly-rising bars ke saath.

Ek-picture summary

Sab kuch ek canvas par: tree $a^i$ nodes aur $n/b^i$ sizes per level ke saath, height ${\log }_{b}n$, $n^{{\log }_{b}a}$ leaves, per-level bar profile, aur teen verdicts (root / flat / leaves win) ratio $r=a/b^c$ se branching off karte hue.