Divide and conquer — template, correctness, recurrence: Question bank

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

Neeche har "true/false" answer ke saath ek reason hai — sirf haan/nahi bolna yahan bilkul bekar hai.

True or false — justify

Zyada subproblems (

a

bada) hamesha divide-and-conquer algorithm ko faster banata hai.

False.

a

exponent

lo g_{b} a

mein baitha hai, isliye

a

badhane se leaf cost

n^{l o g_{b} a}

badhti hai. Karatsuba precisely isliye jeetta hai kyunki usne

a

ko 4 se 3 kar diya, subproblems add karke nahi.

Agar input ke dono halves sahi se solve ho jayein, toh poora answer automatically sahi hoga.

False. Sahi parts tabhi sahi whole dete hain jab combine step khud sahi ho — yeh ek alag proof obligation hai (jaise merge in Mergesort ko apna alag loop-invariant argument chahiye).

Recursion tree method aur Master Theorem alag-alag sets of recurrences solve kar sakte hain.

True. Recursion tree zyada general hai; Master Theorem ek shortcut hai jo tabhi apply hota hai jab

f (n)

polynomially upar/neeche ho

n^{l o g_{b} a}

se, isliye yeh

f (n) = n lo g n

over

n^{1}

jaise gaps par fail ho jaata hai.

Divide-and-conquer ka correctness proof asal mein Mathematical Induction ka proof hota hai.

True. Base case induction ka base hai, recursive calls chote sizes par inductive hypothesis invoke karte hain, aur combine-correctness inductive step hai — recursion tree hi induction tree hai.

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

mein, term

f (n)

recursive calls ki cost count karta hai.

False.

f (n)

sirf non-recursive kaam hai — divide aur combine. Recursive kaam

a T (n / b)

term mein capture hota hai, alag rakha jaata hai taaki hum use unroll kar sakein.

Master Theorem Case 3 ke liye bas itna kaafi hai ki

f (n)

n^{l o g_{b} a}

se tez badhta ho.

False. Iske saath regularity condition

a f (n / b) \leq k f (n)

bhi chahiye kisi

k < 1

ke liye; iske bina ek tez-badhta lekin wildly oscillating

f

Case 3 se bach sakta hai.

Binary search aur mergesort dono Master Theorem Case 2 mein aate hain.

True. Binary Search mein

c_{crit} = lo g_{2} 1 = 0

hai aur

f = Θ (n^{0})

, aur Mergesort mein

c_{crit} = 1

hai aur

f = Θ (n^{1})

— dono mein

f

leaf cost se match karta hai, jisse extra

lo g n

factor milta hai.

Base-case threshold bada karne se asymptotic

O

-class badal jaata hai.

False. Ek constant threshold sirf constants aur low-order terms badalta hai; Big-O class same rehti hai, haalaanki yeh real-world constants mein help kar sakta hai.

Divide and conquer require karta hai ki subproblems independent (non-overlapping) hon.

True. Agar subproblems overlap karte hain aur baar baar solve hote hain, toh aap Dynamic Programming territory mein hain; pure D&C assume karta hai ki pieces shared sub-work nahi karte.

Spot the error

"Mera split length 1 ki array ko [] aur [poori array] mein tod deta hai, aur recursion khud-ba-khud terminate ho jaayega."

Error: koi progress nahi. Ek branch abhi bhi size 1 par hai, isliye kabhi shrink nahi hoti — infinite recursion. Har recursive call ka size strictly smaller hona chahiye, jo ek explicit base case force karta hai.

T (n) = 2 T (n /2) + n lo g n

mein

c_{crit} = 1

hai aur

f = n lo g n > n

, isliye Case 3 se answer

Θ (n lo g n)

hai."

Error:

f

sirf logarithmically upar hai

n^{1}

se, polynomially nahi — isliye Case 3 apply nahi hota. Recursion tree

Θ (n lo g^{2} n)

deta hai.

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

(Karatsuba) ke liye, kyunki

f = n

aur

a = 3

hai, cost

Θ (n \cdot 3) = Θ (n)

hai."

Error: aap

f

a

se simply multiply nahi kar sakte. Yahan

c_{crit} = lo g_{2} 3 \approx 1.585 > 1

hai, isliye

f

leaf cost se neeche hai → Case 1 →

Θ (n^{l o g_{2} 3})

"Maine prove kar diya ki combine correct hai, isliye mera algorithm correct hai."

Error: incomplete proof. Aap abhi bhi progress (har call strictly smaller) aur base correctness (sabse chhote cases sahi) ke liye indebted hain. Koi bhi ek miss karna proof aur code dono tod deta hai.

T (n) = T (n /2) + Θ (1)

mein ek subproblem hai, isliye koi tree nahi hai aur total

Θ (1)

hai."

Error:

a = 1

ke saath tree ek single chain hai jiska height

lo g_{2} n

hai, har node

Θ (1)

kaam karta hai → total

Θ (lo g n)

Θ (1)

nahi.

"Strassen half-size matrices ke 8 multiplications karta hai, jo schoolbook jaisa

Θ (n^{3})

deta hai."

Error: Strassen sirf 7 multiplies karta hai (

a = 7, b = 2

), isliye

c_{crit} = lo g_{2} 7 \approx 2.807

hai aur

T (n) = Θ (n^{2.807})

— strictly

n^{3}

se kam.

Why questions

Hum divide-cost aur combine-cost ko ek

f (n)

mein kyun bundle karte hain?

Kyunki recurrence ke liye hum sirf total non-recursive work per call ki parwah karte hain; unhe alag karna koi naya information nahi deta bas analysis clutter karta hai.

Leaves ki sankhya

n^{l o g_{b} a}

kyun hoti hai, sirf

n

kyun nahi?

lo g_{b} n

levels hain, aur har level node count ko

a

se multiply karta hai, jisse

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

leaves milte hain — branching factor

a

exponent dictate karta hai.

Base case optional kyun nahi hai jab bhi subproblems shrink ho rahe hon?

Kyunki "shrinking" tabhi guaranteed hai jab aap prove karo strict progress; ek bura split ek fixed size par ruk sakta hai, aur bina return-without-recursing rule ke stack overflow ho jaata hai.

Karatsuba mein

a

kam karna (fewer subproblems)

f (n)

kam karne se zyada kyun matter karta hai?

a

exponent

lo g_{b} a

mein rehta hai, jo runtime ki polynomial degree control karta hai;

f

khatraana sirf lower-order terms badalta hai jab aap already leaf-dominated ho.

Same

a

aur

b

wale do algorithms ke alag asymptotic runtimes kyun ho sakte hain?

Kyunki answer

f (n)

n^{l o g_{b} a}

ke relative bhi depend karta hai — ek sasta ya mehanga combine aapko ek alag Master Theorem case mein daal sakta hai.

Recursion ke liye Mathematical Induction natural correctness tool kyun hai, direct loop invariant se zyada?

Recursion same procedure ko chhote inputs par re-invoke karta hai, jo exactly inductive hypothesis "assume it works for size

< n

" ka shape hai — tool structure se match karta hai.

Edge cases

T (n)

kya hoga jab input ka size

0

1

ho?

Yeh definition se

Θ (1)

hai — yahi base case hai, seedha bina recursion ke answer milta hai, aur yahi poori induction ko anchor karta hai.

a = 1

hone par recurrence ka kya hota hai?

"Tree" degenerate ho jaata hai ek chain mein jiska height

lo g_{b} n

hai; koi leaf explosion nahi hota, isliye cost purely us chain ke neeche

f

ke sum se driven hoti hai (jaise Binary Search →

Θ (lo g n)

c_{crit} = lo g_{b} a

kya hoga jab

a < b

, aur iska kya matlab hai?

Yeh negative hota hai (ya, jab

a = 1

ho, zero); yeh signal karta hai ki recursion work ko branching se tez shrink karta hai, isliye

f (n)

almost hamesha dominate karta hai aur aap Case 3 mein jaate ho.

Agar split uneven ho, jaise sizes

n /3

aur

2 n /3

(jaise ek bure Quicksort pivot mein)?

Clean Master Theorem ab apply nahi hota; aap recursion-tree method ya Akra–Bazzi use karte ho, aur unbalanced splits worst case mein Quicksort ko

Θ (n^{2})

ki taraf degrade kar sakte hain.

Runtime kya hoga jab combine step akele

Θ (n^{2})

cost kare jabki

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

ho?

f

leaf cost se polynomially upar hai → Case 3 →

T (n) = Θ (n^{2})

; root ka combine kaam poore tree ko dominate karta hai.

Recall Quick self-test

Is page par sabse common trap ::: $f (n)$ (non-recursive work) ko recursive cost se confuse karna, ya yeh assume karna ki "zyada/chhote subproblems = faster" — yaad rakho $a$ exponent mein rehta hai.