T(n)=2T(n-1)+n2n for n>0, T(0)=1.
Which ONE of the following options is CORRECT?
Correct : a
Given: T(n) = 2T(n − 1) + n2n, T(0) = 1
We need to find the asymptotic bound Θ.
Expand the recurrence
T(n) = 2T(n−1) + n2n
= 2(2T(n−2) + (n−1)2n−1) + n2n
= 4T(n−2) + 2(n−1)2n−1 + n2n
= 4T(n−2) + (n−1)2n + n2n
= 4T(n−2) + (2n − 1)2n
T(n) = 2kT(n−k) + Σi=0k−1 2i(n−i)2n−i
When k = n:
T(n) = 2nT(0) + Σi=0n−1 2i(n−i)2n−i
Simplify the terms
Since 2i × 2n−i = 2n,
T(n) = 2n + 2n Σi=0n−1 (n−i)
Σi=0n−1 (n−i) = n + (n−1) + (n−2) + … + 1 = n(n + 1)/2
T(n) = 2n + 2n × (n(n + 1)/2)
T(n) = 2n (1 + n(n + 1)/2)
As n grows large, dominant term ≈ (n² × 2n).
Therefore: T(n) = Θ(n² × 2n)
Final Answer:
Option A: T(n) = Θ(n² × 2n)
Similar Questions
Total Unique Visitors