Skip to content
GATETECH
Official PYQ · 2025Set 1 · Q10Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2025 Set 1 Q10 — Asymptotic Worst Case Time and Space Complexity

Explain with AI

Consider the following recurrence relation:
T(n)=2T(n−1)+n2n for n>0,T(0)=1T(n)=2 T(n-1)+n 2^{n} \text{ for } n>0, \quad T(0)=1

Which ONE of the following options is CORRECT?

Choose one option
View worked solution

Answer: A

To solve the given recurrence relation:

T(n)=2T(n−1)+n2nfor n>0,T(0)=1T(n) = 2 T(n-1) + n 2^{n} \quad \text{for } n > 0, \quad T(0) = 1

We can simplify it by dividing both sides of the equation by 2n2^n:

T(n)2n=2T(n−1)2n+n2n2n\frac{T(n)}{2^n} = \frac{2 T(n-1)}{2^n} + \frac{n 2^n}{2^n} T(n)2n=T(n−1)2n−1+n\frac{T(n)}{2^n} = \frac{T(n-1)}{2^{n-1}} + n

Let us define a new sequence S(n)=T(n)2nS(n) = \frac{T(n)}{2^n}. Substituting this into the equation gives:

S(n)=S(n−1)+nS(n) = S(n-1) + n

The base case is:

S(0)=T(0)20=11=1S(0) = \frac{T(0)}{2^0} = \frac{1}{1} = 1

Now, we can expand the recurrence for S(n)S(n):

S(n)=S(n−1)+n=S(n−2)+(n−1)+n=S(0)+∑i=1ni=1+n(n+1)2\begin{aligned} S(n) &= S(n-1) + n \\ &= S(n-2) + (n-1) + n \\ &= S(0) + \sum_{i=1}^{n} i \\ &= 1 + \frac{n(n+1)}{2} \end{aligned}

Thus, the asymptotic complexity of S(n)S(n) is:

S(n)=Θ(n2)S(n) = \Theta(n^2)

Substituting back T(n)=2nS(n)T(n) = 2^n S(n):

T(n)=2n(1+n(n+1)2)=Θ(n22n)T(n) = 2^n \left( 1 + \frac{n(n+1)}{2} \right) = \Theta(n^2 2^n)

Therefore, the correct option is A.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Asymptotic Worst Case Time and Space Complexity questions