Runtime recurrences: expansion, trees और Master cases
लक्ष्य और संबंध
मौजूदा discrete recurrence पाठ sequences और initial values पर है। यहाँ recurrence algorithm running time दर्शाती है। पहले asymptotic bounds और logarithms पढ़ें। Input size, base case, recursive sizes तथा nonrecursive work स्पष्ट करें। Powers of b पर T(1)=Θ(1) लें; सामान्य balanced cases में floor/ceiling से asymptotic bound नहीं बदलता।
1. पहले recurrence बनाएँ
दो half-size calls तथा linear combine से T(n)=2T(n/2)+Θ(n), न कि T(n/2)+Θ(n), क्योंकि दोनों calls चलती हैं। Binary search में केवल एक half-size call तथा O(1) बाकी work होता है: T(n)=T(n/2)+Θ(1)=Θ(log n)। हर call के loop को उसी call के subproblem size पर गिनें।
T(n)=T(n−1)+n खोलने पर T(1)+2+3+...+n=Θ(n²)। केवल depth n−1 runtime नहीं; हर level का work अलग है। T(n)=T(n/2)+1, T(1)=1 और n=2^k में k expansions के बाद 1 आता है, इसलिए exact T(n)=k+1। Base value exact answer में जरूरी है।
2. Recursion tree में हर node गिनें
T(n)=2T(n/2)+n, T(1)=1 के level i पर 2^i nodes, प्रत्येक size n/2^i है; कुल nonrecursive work n है। log2 n internal levels और cost 1 वाले n leaves हैं। इसलिए exact T(n)=n log2 n+n; T(8)=32। Leaves को combine-work वाला अतिरिक्त internal level न मानें।
4T(n/2)+n में level i का work n·2^i है। नीचे के levels dominate करते हैं; leaves 4^(log2 n)=n², इसलिए Θ(n²)। 2T(n/2)+n² में level cost n²/2^i है। घटता geometric sum Θ(n²) देता है; root dominates। Tree से बढ़ने/घटने का कारण दिखता है।
3. Standard Master theorem
T(n)=aT(n/b)+f(n), fixed a>=1, b>1 और eventually nonnegative f(n) लें। c=log_b a निकालकर f(n) को n^c से compare करें।
- Case 1: किसी fixed ε>0 के लिए f(n)=O(n^(c−ε))। तब T(n)=Θ(n^c)।
- Basic case 2: f(n)=Θ(n^c)। तब T(n)=Θ(n^c log n)।
- Case 3: fixed ε>0 के लिए f(n)=Ω(n^(c+ε)), और eventually a f(n/b)<=k f(n), जहाँ fixed k<1। तब T(n)=Θ(f(n))। Regularity condition भूलना गलत है।
4T(n/2)+n case 1 है, c=2। 2T(n/2)+n case 2 है, c=1। 2T(n/2)+n² case 3 है: 2(n/2)²=n²/2, अतः k=1/2। Basic case 2 हर logarithmic factor नहीं संभालता। 2T(n/2)+n log2 n में level i cost n(log2 n−i) है; sum Θ(n log² n)। Extended theorem संभव है, लेकिन दिए basic cases में जबरन न रखें।
4. सीमाएँ और जाँच
T(n−1)+n इस Master form में नहीं है। T(n/3)+T(2n/3)+n भी नहीं, क्योंकि recursive sizes अलग हैं। Expansion, सही bounded tree या substitution फिर भी काम आ सकते हैं। Substitution proof में induction hypothesis और additive terms समाने का slack चाहिए; केवल Θ guess proof नहीं है। छोटे n पर जाँचने से missing leaf cost पकड़ सकते हैं। Runtime recurrence को stack-space recurrence न मानें; depth-first execution branches के बीच memory reuse कर सकता है।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. T(n)=2T(n/2)+n, T(1)=1। T(8)?
A. 24 B. 25 C. 32 D. 64
उत्तर: C
A: Leaves छूटे हैं।
B: एक नहीं, आठ leaves हैं।
C: 8·3+8=32।
D: यह recurrence के बजाय n square करता है।
P02. T(n)=T(n−1)+n का order:
A. Θ(log n) B. Θ(n) C. Θ(n log n) D. Θ(n²)
उत्तर: D
A: Size एक घटता है, आधा नहीं।
B: Level cost constant नहीं।
C: Arithmetic sum quadratic है।
D: 1 से n तक sum Θ(n²)।
P03. 4T(n/2)+n कौन-सा basic Master case?
A. Case 1 B. Case 2 C. Case 3 D. None
उत्तर: A
A: c=2 और n, n² से polynomially छोटा है।
B: f, Θ(n²) नहीं।
C: f, n² से बड़ा नहीं।
D: Equal-size form सही है।
P04. 2T(n/2)+n² का order:
A. Θ(n) B. Θ(n log n) C. Θ(n²) D. Θ(n³)
उत्तर: C
A: Root ही n² है।
B: यह linear combine का result है।
C: Case 3 regularity ratio 1/2 है।
D: Geometric decrease extra n नहीं जोड़ता।
P05. दिए equal-size Master form से बाहर कौन है?
A. 2T(n/2)+1 B. 3T(n/3)+n C. T(n/3)+T(2n/3)+n D. T(n/2)+n²
उत्तर: C
A: a=2 वाला equal-size form।
B: a=3 वाला equal-size form।
C: दो अलग recursive sizes हैं।
D: a=1 वाला equal-size form।
P06. 2T(n/2)+n log n का order:
A. Θ(n log n) B. Θ(n log² n) C. Θ(n²) D. Θ(log² n)
उत्तर: B
A: हर level में घटता log factor है।
B: n(log n−i) का sum Θ(n log² n)।
C: Log² n, n से धीमा बढ़ता है।
D: n factor छूटा है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Algorithms syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन