Exercises — Divide and conquer — template, correctness, recurrence

• $a=4$ (char recursive calls), $b=2$ (har child half-size), $f(n)=n$.
• $c_{\text{crit}}={\log }_{2}4=2$.
• $f(n)=n=n^1$ ko $n^2$ se compare karo: $1<2$ hai, isliye $f$ polynomially chhota hai ⟹ Case 1.
• Answer: $T(n)=\Theta (n^2)$.

• "Array ko aadha kato" Divide hai — yeh do subproblems produce karta hai.
• merge Combine hai — yeh do sorted halves ko ek sorted whole mein glue karta hai.
• Do recursive mergesort calls Conquer phase hain.

• Binary Search → $T(n/2)+\Theta (1)$ (ek recursive call, constant compare).
• Mergesort → $2T(n/2)+\Theta (n)$ (do halves, linear merge).
• Karatsuba → $3T(n/2)+\Theta (n)$ (teen half-size multiplications, linear add/shift).

• $a=9,b=3,f(n)=n$.
• $c_{\text{crit}}={\log }_{3}9=2$.
• $f(n)=n=n^1$ vs $n^2$: $1<2$ ⟹ Case 1.
• $T(n)=\Theta (n^2)$.

• $a=2,b=2,f(n)=n^2$; $c_{\text{crit}}={\log }_{2}2=1$.
• $f(n)=n^2$ vs $n^1$: $2>1$, isliye $f$ polynomially bada hai ⟹ candidate Case 3.
• Regularity check: $af(n/b)=2(n/2{)}^2=2\cdot n^2/4=n^2/2=\frac{1}{2}f(n)$. $k=\frac{1}{2}<1$ ke saath ✓.
• Case 3 confirmed: $T(n)=\Theta (f(n))=\Theta (n^2)$.

• $a=7,b=2,f(n)=n^2$; $c_{\text{crit}}={\log }_{2}7\approx 2.807$.
• $f(n)=n^2$ vs $n^{2.807}$: $2<2.807$ ⟹ $f$ chhota hai ⟹ Case 1.
• $T(n)=\Theta (n^{{\log }_{2}7})\approx \Theta (n^{2.807})$.
• Matlab: Strassen naive $\Theta (n^3)$ matrix multiply ko beat karta hai kyunki ${\log }_{2}7<3$.

• $a=2,b=2$, isliye $c_{\text{crit}}=1$ aur $n^{c_{\text{crit}}}=n$. Yahan $f(n)=n\log n$.
• Kya $f$ polynomially bada hai $n$ se? Humein chahiye hoga $n\log n=\Omega (n^{1+\epsilon })$ kisi $\epsilon >0$ ke liye. Lekin $\log n$ har $\epsilon >0$ ke liye $n^{\epsilon }$ se dhire badhta hai, isliye aisa koi $\epsilon$ exist nahi karta. Gap sirf logarithmic hai: $f$ na polynomially chhota hai (Case 1), na $\Theta (n)$ (plain Case 2), na polynomially bada (Case 3). Isliye plain three-case statement koi answer nahi deta. (Yeh hamare upar ke definition se generalized Case 2 with $k=1$ mein cover hota hai — aur hum woh answer neeche haath se confirm karte hain.)
• Recursion tree. Level $i$ mein $2^i$ nodes hain har ek size $n/2^i$ ke, $f(n/2^i)=\frac{n}{2^i}\log \frac{n}{2^i}$ work karte hue. Level total: $2^i\cdot \frac{n}{2^i}\log \frac{n}{2^i}=n\log \frac{n}{2^i}=n(\log n-i).$
• $i=0$ se ${\log }_{2}n-1$ tak sum karo: ${\sum }_{i=0}^{{\log }_{2}n-1}n(\log n-i)=n{\sum }_{j=1}^{{\log }_{2}n}j=n\cdot \frac{(\log n)(\log n+1)}{2}=\Theta (n{\log }^{2}n).$
• Answer: $T(n)=\Theta (n{\log }^{2}n)$ — generalized Case 2 se match karta hai ($c_{\text{crit}}=1,k=1\Rightarrow n^1{\log }^{2}n$).

• Do children alag alag factors se shrink karte hain, isliye plain MT (jise ek clean $b$ chahiye) apply nahi hota.
• Pehle ek monotonicity note. Neeche ke sab bounds use karte hain ki $T$ nondecreasing hai $n$ mein (bada input ⟹ utna hi ya zyada kaam). Yeh hold karta hai kyunki recurrence ka non-recursive term $n$ nondecreasing hai aur recursive calls nonnegative sizes par hain, isliye ek standard induction dikhata hai ki $T(m)\le T(n)$ jab bhi $m\le n$. Hum yeh poori jagah assume karte hain.
• Upper bound. Kyunki $T$ nondecreasing hai, $T(n/4)\le T(n/2)$, isliye chhote child ko bade se replace karne par total sirf badh sakta hai: $T(n)\le 2T(n/2)+n$, jo Case 2 hai ⟹ $O(n\log n)$.
• Lower bound. Root akela $n$ kaam karta hai, isliye $T(n)=\Omega (n)$.
• Kyun har level par total input size $\frac{3}{4}$ se multiply hoti hai. Size $s$ ka har node do children spawn karta hai sizes $s/2$ aur $s/4$ ke, jinki sizes add karke $s/2+s/4=\frac{3}{4}s$ hoti hai. Isliye agar level $i$ par sab nodes ki sizes add karke $S_i$ hain, toh har node par yeh sum karne se $S_{i+1}=\frac{3}{4}{S}_i$ milta hai. $S_0=n$ (root) se shuru karke, $S_i=n(\frac{3}{4}{)}^i$ milta hai.
• Sharper tree sum. Ek node par non-recursive work uski size ke barabar hai (yeh $+n$ term linear hai), isliye level-$i$ work $=S_i=n(\frac{3}{4}{)}^i$, ek geometric series: ${\sum }_{i\ge 0}n{\left(\frac{3}{4}\right)}^i=n\cdot \frac{1}{1-\frac{3}{4}}=4n=\Theta (n).$
• Kyunki series converge karti hai, root dominate karta hai: $T(n)=\Theta (n)$ (jo upar ke loose $O(n\log n)$ upper bound ko bhi tighten karta hai).

• Guess: $T(n)\le cn{\log }_{2}n$. Hum $c$ find karte hain 2 ki powers par induction se.
• Base $n=2$: $T(2)=2T(1)+2=2\cdot 1+2=4$. Humein chahiye $c\cdot 2\cdot {\log }_{2}2=2c\ge 4$, yani $c\ge 2$.
• Step: assume karo $T(n/2)\le c\frac{n}{2}{\log }_2\frac{n}{2}$. Tab $T(n)=2T(n/2)+n\le 2\cdot c\frac{n}{2}{\log }_2\frac{n}{2}+n=cn({\log }_{2}n-1)+n=cn{\log }_{2}n-cn+n.$
• Yeh $\le cn{\log }_{2}n$ hai iff $-cn+n\le 0$, yani $c\ge 1$. Base ke $c\ge 2$ ke saath mila ke, $c=2$ choose karo.
• Isliye $T(n)\le 2n{\log }_{2}n=O(n\log n)$. ∎

• Header se yaad karo ki non-recursive term hai $f(n)=D(n)+C(n)$: divide cost plus combine cost.
• Divide: array ko left aur right halves mein split karo ($a=2$, $b=2$; split sirf index arithmetic hai, isliye $D(n)=\Theta (1)$).
• Conquer: har half ka max recursively dhundho.
• Combine: do returned maxima mein se bada return karo — ek comparison, isliye $C(n)=\Theta (1)$.
• Isliye $f(n)=D(n)+C(n)=\Theta (1)+\Theta (1)=\Theta (1)$.
• Base: ek akela element apna khud ka max hai.
• Recurrence: $T(n)=2T(n/2)+\Theta (1)$. Tab $a=2,b=2,c_{\text{crit}}=1$, $f(n)=\Theta (1)=\Theta (n^0)$; $0<1$ ⟹ Case 1 ⟹ $T(n)=\Theta (n^1)=\Theta (n)$.
• Comparison: linear scan jaisa hi $\Theta (n)$ — divide and conquer yahan kuch nahi kama raha kyunki koi cheap combine advantage nahi hai; har element phir bhi ek baar dekhna padta hai. (Useful lesson: D&C tabhi jeeтта hai jab combine re-solving se sasta ho.)

• Proposal valid nahi hai: har sorted array ko "aadha" split karke crosswise merge karne par, jo halves tum pick karte ho woh cleanly interleave hone ki guarantee nahi — array A ke left half ka element array B ke right half ke kisi element se bada ho sakta hai, isliye charo merges overlap karte hain. Subproblems independent nahi hain, jo paradigm ki precondition tod deta hai.
• Correct merge ek single linear pass hai do pointers ke saath: $\Theta (n)$, merge ke andar khud koi recursion nahi.
• Mergesort ke andar poori recurrence hai $T(n)=2T(n/2)+\Theta (n)$ jahan $\Theta (n)$ yahi two-pointer merge hai. Case 2 ⟹ $\Theta (n\log n)$.

• Naya: $a=5,b=3$, $c_{\text{crit}}={\log }_{3}5\approx 1.4650$.
• $f(n)=n=n^1$; $1<1.465$ ⟹ Case 1 ⟹ $T(n)=\Theta (n^{{\log }_{3}5})\approx \Theta (n^{1.465})$.
• Karatsuba hai $\Theta (n^{{\log }_{2}3})\approx \Theta (n^{1.585})$.
• Kyunki $1.465<1.585$, naya scheme asymptotically faster hai. (Yeh real Toom–3 algorithm hai.)

• $c_{\text{crit}}={\log }_{2}a$; $f(n)=n=n^1$ ko $n^{{\log }_{2}a}$ se compare karo.
• $a<2$: ${\log }_{2}a<1$, isliye $f$ bada hai ⟹ Case 3 (regularity: $a\cdot \frac{n}{2}=\frac{a}{2}n$ with $k=\frac{a}{2}<1$ ✓) ⟹ $T(n)=\Theta (n)$.
• $a=2$: ${\log }_{2}a=1$, tie ⟹ Case 2 ⟹ $T(n)=\Theta (n\log n)$.
• $a>2$: ${\log }_{2}a>1$, leaves bade ⟹ Case 1 ⟹ $T(n)=\Theta (n^{{\log }_{2}a})$.
• Single transition point hai $a=2$: us se neeche root dominate karta hai ($\Theta (n)$), exactly us par har level tie karta hai ($\Theta (n\log n)$), aur us se upar leaves dominate karte hain ($\Theta (n^{{\log }_{2}a})$).

• Tree ki depth $L={\log }_{b}n$ hai (har step size ko $b$ se divide karta hai jab tak size 1 na ho: $n/b^L=1$).
• Claim: level $i$ par $a^i$ nodes hain. Base $i=0$: ek root, $a^0=1$ ✓. Step: agar level $i$ par $a^i$ nodes hain aur har ek $a$ children spawn karta hai, toh level $i+1$ par $a\cdot a^i=a^{i+1}$ ✓. Induction se claim sab $i$ ke liye hold karta hai.
• Leaves $i=L={\log }_{b}n$ par baithe hain, isliye unki count hai $a^L=a^{{\log }_{b}n}.$
• $a^{{\log }_{b}n}$ ko $n^{{\log }_{b}a}$ ke roop mein likhein. Left side ka natural log lo: $\ln \left(a^{{\log }_{b}n}\right)=({\log }_{b}n)(\ln a)=\frac{\ln n}{\ln b}\ln a$. Right side ka natural log lo: $\ln \left(n^{{\log }_{b}a}\right)=({\log }_{b}a)(\ln n)=\frac{\ln a}{\ln b}\ln n$. Dono $\frac{\ln a\ln n}{\ln b}$ ke barabar hain, aur $\ln$ one-to-one hai, isliye original quantities equal hain: $a^{{\log }_{b}n}=n^{{\log }_{b}a}.$
• Isliye leaves ki sankhya $n^{{\log }_{b}a}$ hai. Har leaf $\Theta (1)$ kaam karta hai, isliye total leaf work $=n^{{\log }_{b}a}\cdot \Theta (1)=\Theta (n^{{\log }_{b}a})$. Yeh exactly parent note se watershed cost $n^{c_{\text{crit}}}$ hai. ∎

• $f$ ko poori range mein same case mein rakho. Lo $f(n)=n^3$ aur $b=2$, toh $c_{\text{crit}}={\log }_{2}a$ ranges from $0$ ($a=1$ par) se $3$ ($a=8$ par) tak.
• $f(n)=n^3$ ko strictly dominant term rakhne ke liye humein chahiye $c_{\text{crit}}<3$, yani ${\log }_{2}a<3$, yani $a<8$. Isliye $a\in \{1,\dots ,7\}$ ke liye: $f=n^3$ polynomially bada hai $n^{c_{\text{crit}}}$ se ⟹ Case 3 ⟹ $T(n)=\Theta (n^3)$, $a$ se independent.
• Kyun unchanged: Case 3 mein root work $f(n)$ poore sum ko dominate karta hai; subproblems ki sankhya sirf (geometrically chhote) neeche ke levels ko affect karti hai, jo constant mein collapse ho jaate hain. $a$ ko root-heavy regime ke andar badhane se asymptotics touch nahi hoti.
• Isliye student galat hai: $a$ tabhi matter karta hai jab woh tumhe case boundary ke across push kare (yahan, $a=8$ tak pahunchne par jahan $c_{\text{crit}}=3$ hai jo $f$ se tie karta hai aur Case 2 mein flip hota hai, $\Theta (n^3\log n)$).

Leaf exponent hai ==$c_{\text{crit}}={\log }_{b}a$==. Master Theorem ke plain three cases fail hote hain jab $f(n)$ aur $n^{c_{\text{crit}}}$ ke beech gap sirf logarithmic (not polynomial) ho. Case 3 ke liye extra regularity condition $af(n/b)\le kf(n)$ with $k<1$ chahiye.