3.7.2 · D1Divide and conquer — template, correctness, recurrence
Size n chhoti copies of same problem mein solve kiya ja sakta hai, aur phir answers ko saste mein glue karke final answer banaya jaata hai. Divide and conquer bas yahi bet hai — split + glue, brute force se sasta hai — saath mein bookkeeping (ek recurrence) jo exactly batata hai ki yeh bet kitni tezi se pay off karta hai.
Pehle aapko parent note ki ek bhi line padhne se pehle, usme aane wale har symbol ko khud se samajhna hoga. Yeh page har ek ko ground up se build karta hai: seedhe words → ek picture → kyun is topic ko iska zaroorat hai. Kuch bhi assume nahi kiya gaya.
n n jo cheez aapko process karni hai woh kitni badi hai . Sort karne ke liye ek list mein, n n
Picture: imagine karo ek row of boxes. Unhe gino. Woh count hai n
Intuition "Size" ki zaroorat kyun haiSpeed ke baare mein har claim — "yeh fast hai", "yeh slow hai" — meaningless hai jab tak hum nahi kehte kis size ke liye fast? 3 items sort karna trivial hai; 3 billion nahi. Poora subject is baare mein hai ki effort kaise badhta hai jab n , isliye n
Jab hum divide karte hain, do alag numbers split ko describe karte hain. Inhe confuse mat karo .
a a a = 2 a = 3
b chhota hai)
Har subproblem ki size lagbhag n / b n /2 b = 2 b size ko divide karte ho — yeh size ke baare mein hai, count ke nahi.
Common mistake Steel-man: "a b Kyun sahi lagta hai: mergesort mein aap 2 halves mein kaatte ho aur dono par recurse karte ho, toh a = 2 b = 2 happen to match karte hain.
Kyun galat hai: woh alag cheezein measure karte hain. Karatsuba mein aap har number ko 2 halves mein kaatte ho (b = 2 a = 3 b = 2 a = 1 Fix: do alag sawaal pucho — "kitna chhota?" se b "main kitne ko rakhta hoon aur solve karta hoon?" se a
Definition Recursion = ek procedure jo khud ko call karta haiEk recursive procedure ek problem ko solve karta hai asking a smaller copy of itself to solve smaller pieces , phir unhe answers use karke. Picture hai nested boxes ka ek set: har box ka kaam hai chhote boxes chalana aur unke outputs combine karna.
Definition Base case = sabse chhoti problem, seedha answer denaBase case itni chhoti size hai ki answer ko koi recursion nahi chahiye — length 1 floor hai jo nesting ko rokta hai.
Intuition Base case optional kyun nahi haiFloor ke bina, boxes forever nest karte hain — program ya toh endlessly chalta hai ya crash karta hai (ek stack overflow , jab paused calls ka dher memory se zyada ho jaata hai). Base case hi woh cheez hai jo guarantee karta hai ki recursion kabhi rukta hai. Parent note ka pehla "steel-man" bilkul isi trap ke baare mein hai.
Poori recursion machinery aapko phir Mathematical Induction mein milegi aur aap dekhoge ki yeh Mergesort , Quicksort , aur Binary Search ko power karta hai.
Definition Combine = sub-answers ko poore answer mein glue karnaJab a merge hai: do sorted halves ko walk karke unhe ek sorted list mein interleave karna.
f ( n ) f ( n ) recursive call nahi hain : split karne ka kaam (divide) plus glue karne ka kaam (combine), size n
Intuition Divide aur combine ko bundle kyun karein?Jab hum baad mein cost add karte hain, sirf do tarah ka kaam hota hai: kaam jo recursive calls ke andar hota hai, aur kaam jo yahan, abhi, is level par hota hai. Doosre tarah ke kaam ko f ( n ) "mera time = mere subcalls ka time + mera apna local kaam."
T ( n ) n T n guarantee hai, kabhi underestimate nahi.
Aise equations ko actually solve karna aap Recurrence Relations mein seekhoge.
log b n n b 1 n b b 1 Divisions ki sankhya hai log b n b n
Concrete: b = 2 n = 8 8 → 4 → 2 → 1 3 steps lagte hain, toh log 2 8 = 3
Intuition Log yahan har jagah kyun aata haib tree of levels banata hai. Us tree ki height — nesting kitni gahari jaati hai base case hit hone se pehle — exactly halvings ki sankhya hai, log b n "recursion kitna tall hai?" Yahi woh tool hai jo hamein chahiye, aur koi simpler tool "kitni baar half kar sakta hoon?" ka answer nahi deta.
a i a i i a a 0 1 1 a i a i
Intuition Watershed ek sentence meinHar recurrence leaves (bahut se chhote problems, cost n l o g b a local work f ( n ) ke beech ek tug-of-war hai. Jo bhi n T ( n )
Definition Teen growth symbolsYeh describe karte hain ki ek cost n kaise badhta hai , constant factors aur small terms ignore karke.
O ( g ) g Ω ( g ) g Θ ( g ) exactly g badhta hai (dono ek saath — ek tight sandwich).
Intuition Constants kyun ignore karein?3 n 10 n n straight line ki tarah badhte hain; slope alag hai lekin shape — woh cheez jo decide karti hai kaun jeetta hai jab n → ∞ shapes compare kar sakte hain, jo scaling ke baare mein hai. Poori details Big-O Notation mein hain.
log base b of n = tree height
watershed exponent log base b of a
Divide and Conquer analysis
Sab kuch jo upstream hai woh do cheezein feed karta hai jo parent note actually karta hai : correctness prove karna (recursion = Mathematical Induction ke zariye) aur speed dhundhna (recurrence + Master Theorem ke zariye, Mergesort , Binary Search , Karatsuba , Strassen Matrix Multiplication par apply hota hai, aur Dynamic Programming se contrast kiya jaata hai).
Khud ko test karo — right side cover karo aur zyaane se jawab do.
n Input ki size (jaise list mein items ki sankhya).
a Unhe subproblems ki sankhya jo aap split karne ke baad actually solve karte ho.
b Woh factor jisse input size shrink hota hai; har subproblem ki size n / b
a = b Woh alag cheezein count karte hain — b a b = 2 a = 1
Base case kya hai aur kyun zaruri hai? Sabse chhota input, recursion ke bina answer diya jaata hai; yeh woh floor hai jo nesting ko rokta hai taaki program terminate ho.
f ( n ) Ek level par non-recursive local kaam: divide cost plus combine cost.
Recurrence T ( n ) = a T ( n / b ) + f ( n ) Size n a n / b
log b n Kitni baar aap n b 1
c crit = log b a Watershed exponent; n l o g b a f ( n )
O Ω Θ Di gayi function se zyada tezi se nahi badhta (ceiling), dhheemi se nahi badhta (floor), aur exactly jaisa badhta hai (tight).
Recall Quick self-quizAgar n = 16 b = 2 log 2 16 = 4 a = 3 log 2 n 3 l o g 2 n = n l o g 2 3 ≈ n 1.585
