Question 31
Solve the recurrence T(n) = T(n-1) + $2^n$ with T(0) = 1.
Detailed Solution
$T(n) = 1 + 2^1 + 2^2 + ... + 2^n = 2^{n+1} - 1 = \Theta(2^n).$
✓ Saved
GATE CSE Algorithms – Time Complexity, Recurrences & Amortized Analysis Practice Test | Set 1
Your score
0/100
0 answered
Correct 0
Incorrect 0
Unanswered 100
Accuracy 0%
Question 32
What is the time complexity of the Fibonacci recurrence T(n) = T(n-1) + T(n-2) + O(1)?
Detailed Solution
The characteristic equation $r^2 - r - 1$ = 0 has roots $\phi = (1 + sqrt(5))/2 \approx 1.618$ and psi. Thus T(n) = $\Theta(\phi^n)$.
✓ Saved
Question 33
For the recurrence T(n) = 16 T(n/4) + n!, what is the asymptotic solution?
Detailed Solution
$a=16, b=4, n^{log_4 16} = n^2$. f(n) = n! which grows vastly faster than $n^2$. By Master Theorem Case 3, T(n) = $\Theta(n!)$.
✓ Saved
Question 34
What is the asymptotic bound for T(n) = T(n - 2) + n?
Detailed Solution
$T(n) = n + (n-2) + (n-4) + ... \approx (n/2) * (n/2) = \Theta(n^2).$
✓ Saved
Question 35
Solve T(n) = 8 T(n/2) + $n^3$.
Detailed Solution
$a=8, b=2, n^{log_2 8} = n^3$. $f(n) = n^3$. By Master Theorem Case 2 ($k=0), T(n) = \Theta(n^3 log n$).
✓ Saved