Recursion tree method — Hinglish notes

3.1.9 · Coding › Complexity Analysis

Recursion tree kya hota hai?

Kisi bhi tree ke liye teen sawaal jo tumhe zaroor poochne chahiye:

KITNA DEEP hai ye? (levels ki sankhya) — ye is baat se control hoti hai ki $n$ kitni tezi se shrink hota hai.
HAR LEVEL KITNA WIDE hai? (depth $i$ par nodes ki sankhya) — ye branching $a$ se control hota hai.
HAR LEVEL MEIN KITNA KAAM? (depth $i$ par node values ka sum).

Phir $T (n) = \sum_{levels i} (work at level i)$ .

Level counts ko scratch se derive karna

Standard divide-and-conquer recurrence lo: $T (n) = a T (n / b) + f (n), a \geq 1, b > 1.$

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

Yahan $a = 2, b = 2, f (n) = n$ .

Step	Hum kya karte hain	Ye step kyun?
Depth	$lo g_{2} n$ levels	Size har level halve hoti hai: $n / 2^{i} = 1 \Rightarrow i = lo g_{2} n$ .
Level $i$ par nodes	$2^{i}$	Branching factor $a = 2$ .
Level $i$ par node size	$n / 2^{i}$	Size $b = 2$ se shrink hoti hai.
Har level par kaam	$2^{i} \cdot \frac{n}{2 ^{i}} = n$	$2^{i}$ cancel ho jaata hai — har level $n$ cost karti hai.
Total	$n \times (lo g_{2} n + 1) = Θ (n lo g n)$	Har level barabar kaam × levels ki sankhya.

Worked Example 2 — $T (n) = 3 T (n /4) + n^{2}$

Yahan $a = 3, b = 4, f (n) = n^{2}$ .

Step	Result	Ye step kyun?
Level $i$ par kaam	$3^{i} (\frac{n}{4 ^{i}})^{2} = n^{2} (\frac{3}{16})^{i}$	$a^{i} f (n / b^{i})$ mein plug karo; $i$ ki powers group karo.
Ratio	$\frac{3}{16} < 1$	Ratio $< 1$ wali geometric series → decreasing.
Sum	$n^{2} \sum_{i} (3/16)^{i} \leq n^{2} \cdot \frac{1}{1 - 3/16} = Θ (n^{2})$	Convergent geometric series → constant factor.
Total	$Θ (n^{2})$	Root dominate karta hai — top level ka kaam jeet jaata hai.

Worked Example 3 — Unbalanced tree: $T (n) = T (n /3) + T (2 n /3) + n$

Subproblems alag alag rates se shrink karte hain, isliye hum directly $b$ use nahi kar sakte. Hum height ko bound karte hain.

Step	Result	Ye step kyun?
Har level par kaam	$\leq n$ (ek level par sizes $\leq n$ tak sum hoti hain)	$n /3 + 2 n /3 = n$ ; cost $f$ linear hai, to har level lagbhag $n$ tak sum hoti hai.
Sabse chhota path	$lo g_{3} n$ (3 se divide)	$1/3$ wali branch sabse tezi se shrink karti hai.
Sabse lamba path	$lo g_{3/2} n$ ( $2/3$ se multiply)	$2/3$ wali branch sabse dheere shrink karti hai → sabse gehra.
Total	$n lo g_{3} n$ aur $n lo g_{3/2} n$ ke beech → $Θ (n lo g n)$	Levels $\times$ per-level kaam $n$ , saare logs constants se alag hain.

Common mistake Classic blunders ko steel-man karna

Mistake A: "Har level $f (n)$ cost karti hai, to total = $f (n) \cdot lo g n$ ." Kyun sahi lagta hai: Merge sort mein har level sach mein $n$ cost karti hai, to log iske baad overgeneralize karte hain. Fix: Level cost $a^{i} f (n / b^{i})$ hai, $f (n)$ nahi. Ye tabhi constant rehta hai jab $a^{i}$ exactly $f$ ki shrink ko cancel kare. Hamesha per-level sum calculate karo.

Mistake B: "Leaves ki sankhya $n$ hai." Kyun sahi lagta hai: Merge sort ke liye leaves sach mein $n$ hain (kyunki $n^{l o g_{2} 2} = n$ ). Fix: Leaves $= a^{l o g_{b} n} = n^{l o g_{b} a}$ . $a = 3, b = 2$ ke liye ye $n^{1.58}$ hai, $n$ nahi.

Mistake C: Geometric ratio ki direction bhool jaana. Kyun sahi lagta hai: Log bina growth check kiye " $lo g n$ levels of something" sum kar lete hain. Fix: Ratio $r = a / b^{d}$ compute karo (jahan $f = n^{d}$ ). $r < 1$ →root, $r = 1$ → $lo g$ factor, $r > 1$ →leaves.

80/20 takeaway

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

Ek boss ko ek bada kaam socho. Wo ise chote chote kaamon mein todta hai aur helpers ko deta hai. Har helper apna kaam aur todta hai, aur aisa tab tak chalta hai jab tak kaam bahut chota na ho jaaye. Ise jobs ki ek family tree ki tarah draw karo. Ye jaanne ke liye ki poori company ne kitna kul effort kiya, har insaan ke paas effort likh do aur sab ko add karo — row by row karna aasaan hai. Kabhi kabhi boss sabse zyada kaam karta hai (tree ka top), kabhi bottom par chote workers (kyunki wo BAHUT ZYADA hain), aur kabhi sabhi barabar kaam karte hain. Recursion tree bas ye dekhne mein madad karta hai ki heavy lifting kaun kar raha hai.

Flashcards

Kisi bhi recursion tree ke liye teenon kaunsi quantities dhundni chahiye?

Depth (

lo g_{b} n

), nodes per level (

a^{i}

), aur work per level (

a^{i} f (n / b^{i})

T (n) = a T (n / b) + f (n)

ke liye recursion tree se total-work formula?

T (n) = \sum_{i = 0}^{l o g_{b} n} a^{i} f (n / b^{i})

Tree mein kitne leaves hote hain?

a^{l o g_{b} n} = n^{l o g_{b} a}

, har ek ka cost

Θ (1)

Merge sort

2 T (n /2) + n

ke liye per-level kaam aur kyun constant hai?

2^{i} \cdot (n / 2^{i}) = n

; branching

2^{i}

shrink ko cancel kar deta hai, to har level

n

cost karti hai → total

Θ (n lo g n)

T (n) = 3 T (n /4) + n^{2}

ke liye level-

i

kaam aur answer kya hai?

n^{2} (3/16)^{i}

; ratio

< 1

→ root dominate karta hai →

Θ (n^{2})

Root kab dominate karta hai vs leaves?

Root dominate karta hai jab per-level kaam decreasing geometric series hoti hai (

a < b^{d}

); leaves dominate karti hain jab growing hoti hai (

a > b^{d}

Ek unbalanced tree jaise

T (n /3) + T (2 n /3) + n

Θ (n lo g n)

kyun deta hai?

Har level

\leq n

tak sum hoti hai aur height

lo g_{3} n

aur

lo g_{3/2} n

ke beech hai, ye sab

Θ (lo g n)

hain.

Galat leaf count aur uska fix?

n

leaves" bolna; sahi hai

n^{l o g_{b} a}

(sirf

n

ke barabar hota hai jab

a = b

Connections

Master Theorem — recursion tree uska proof/intuition engine hai.
Big-O Notation — level sums asymptotic notation se bound ki jaati hain.
Divide and Conquer — har D&C algorithm ek recursion tree produce karta hai.
Geometric Series — root vs leaves decide karna ek geometric-series convergence test hai.
Merge Sort aur Binary Search — canonical balanced/decreasing trees.
Substitution Method — alternative recurrence-solving technique (guess + induction).