Computer Sciences > GATE 2025 SET-1 > Recurrence Relations
Consider the following recurrence relation:
T(n)=2T(n-1)+n2n for n>0, T(0)=1.
Which ONE of the following options is CORRECT?
A
T(n)=Θ(n22n)
B
T(n)=Θ(n2n)
C
T(n)=Θ((log n)22n)
D
T(n)=Θ(4n)

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

Consider the following recurrence relation: Which one of the following options is CORRECT?
#878 MCQ
Consider the following recurrence relation: Which one of the following options is CORRECT?
#878 MCQ
Consider the following recurrence relation: Which one of the following options is CORRECT?
#878 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......