Master theorem — solving recurrences T(n) = aT(n - b) + f(n)

3.1.7 · Coding › Complexity Analysis

Symbols ka matlab (KYA HAI)

Number $n^{l o g_{b} a}$ leaves ka total cost hai. Sab kuch tumhare combine-cost $f (n)$ ko isse compare karne par depend karta hai.

Scratch se derive karo (KAISE — kabhi bhi formula par andha bharosa mat karo)

Recursion ko ek tree mein unroll karo.

Level 0 (root): 1 node, kaam $f (n)$ .
Level 1: $a$ nodes, har ek ka kaam $f (n / b)$ → total $a f (n / b)$ .
Level $i$ : $a^{i}$ nodes, har ek ki size $n / b^{i}$ , kaam $a^{i} f (n / b^{i})$ .
Last level: size tab 1 hoti hai jab $n / b^{L} = 1 \Rightarrow L = lo g_{b} n$ .

Ab leaves gino. Leaves ki sankhya hai: $a^{l o g_{b} n} = n^{l o g_{b} a} = n^{c_{crit}} .$ Kyun? Use karo $a^{l o g_{b} n} = (b^{l o g_{b} a})^{l o g_{b} n} = b^{l o g_{b} a \cdot l o g_{b} n} = (b^{l o g_{b} n})^{l o g_{b} a} = n^{l o g_{b} a}$ . Toh leaf cost $= Θ (n^{l o g_{b} a})$ .

Sum essentially ek geometric series hai jo $f (n)$ ko $n^{l o g_{b} a}$ se compare karta hai:

Agar $f$ chhoti ho ( $f = O (n^{l o g_{b} a - ϵ})$ ): series neeche ki taraf grow karti hai, leaves dominate karti hain → $T (n) = Θ (n^{l o g_{b} a})$ .
Agar $f$ equal ho ( $f = Θ (n^{l o g_{b} a})$ ): har level ka cost lagbhag same hota hai, aur $lo g_{b} n$ levels hain → $lo g n$ se multiply karo.
Agar $f$ badi ho ( $f = Ω (n^{l o g_{b} a + ϵ})$ ): root dominate karta hai → $T (n) = Θ (f (n))$ (ek regularity check chahiye taaki series actually root par converge kare).

Teeno cases (woh 20% jo tumhe memorize karna hi hai)

Figure — Master theorem — solving recurrences T(n) = aT(n - b) + f(n)

Forecast-then-Verify worked examples

YEH KAB TOOT-TA HAI (apni galtiyon ko steel-man karo)

Quick decision recipe (80/20)

$p = lo g_{b} a$ aur leaf cost $n^{p}$ compute karo.
Polynomially chhota $f$ → Case 1 → answer $n^{p}$ .
Equal (upto $lo g^{k}$ tak) → Case 2 → answer $n^{p} lo g^{k + 1} n$ .
Polynomially bada $f$ + regularity → Case 3 → answer $f (n)$ .
Cases ke beech sirf ek log gap ho → basic Master nahi; extended Case 2 use karo.

Recall Feynman: ek 12-saal ke bachche ko samjhao (click to reveal)

Socho ek kaam hai jo tum dosto mein baant dete ho. Har round mein tum har dost ko ek chhota kaam dete ho, lekin saath mein khud bhi kuch sorting ka kaam karte ho. Do costs ladte hain: neeche bahut saare tiny chores ka giant pile vs upar tumhara bada sorting kaam. Master Theorem bas ek referee hai: dekho kitni tezi se chores multiply ho rahe hain ( $a$ ) versus kitni tezi se shrink ho rahe hain ( $b$ ). Agar tiny chores tumhe daba dein, answer leaf cost hai. Agar tumhari apni sorting tumhe daba de, answer top cost hai. Agar tie ho, har floor par same cost pay karte ho, toh floors ki sankhya ( $lo g n$ ) se multiply karo.

Connections

Recursion Trees — woh visual derivation jo Master Theorem summarize karta hai.
Akra–Bazzi method — unequal subproblems / non-constant splits ke liye generalization.
Big-O, Big-Omega, Big-Theta — asymptotic comparison machinery.
Merge Sort, Karatsuba Multiplication, Binary Search — direct applications.
Geometric Series — kyun teeno cases exist karte hain (increasing/flat/decreasing series).

Flashcards

Master Theorem recurrence ko define karne wale teeno quantities kya hain?

a

= subproblems ki sankhya,

b

= shrink factor (

n \to n / b

f (n)

= recursion ke bahar kaam (split+combine).

Critical exponent kya hai aur

n^{l o g_{b} a}

kya represent karta hai?

c_{crit} = lo g_{b} a

;

n^{l o g_{b} a}

recursion tree ki leaves ka total cost hai.

Master Theorem ka Case 1 batao.

Agar

f (n) = O (n^{l o g_{b} a - ϵ})

, toh

T (n) = Θ (n^{l o g_{b} a})

(leaves jeette hain).

Case 2 (extended) batao.

Agar

f (n) = Θ (n^{l o g_{b} a} lo g^{k} n)

, toh

T (n) = Θ (n^{l o g_{b} a} lo g^{k + 1} n)

Case 3 aur uski extra condition batao.

Agar

f (n) = Ω (n^{l o g_{b} a + ϵ})

AUR

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

kisi

c < 1

ke liye, toh

T (n) = Θ (f (n))

Case 2 mein

lo g n

se kyun multiply karte hain?

Har level ka cost same hota hai (

Θ (n^{l o g_{b} a})

) aur

lo g_{b} n

levels hote hain, toh total = level cost × levels ki sankhya.

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

solve karo.

c_{crit} = 1

f = n = Θ (n^{1})

→ Case 2 →

Θ (n lo g n)

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

solve karo.

c_{crit} = 0

f = 1 = Θ (n^{0})

→ Case 2 →

Θ (lo g n)

(binary search).

Basic Master Theorem

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

kyun solve nahi kar sakta?

n lo g n

n

se sirf ek log factor se zyada hai, polynomial factor se nahi — gap mein aata hai; extended Case 2 deta hai

Θ (n lo g^{2} n)

Leaves ki sankhya

n^{l o g_{b} a}

kyun hai?

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

Master Theorem kab apply NAHI hota?

Jab

a, b

non-constant hon; unequal subproblem sizes (e.g.

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

); non-polynomial gaps; negative

f