Consider the following recurrence relation: \(T(n) = 2T(n - 1) + n 2^n, \quad…

GATE · 2025 · CS · Set 1 · Computer Science & IT

Consider the following recurrence relation:

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

Which ONE of the following options is CORRECT?

  1. A.

    T(n)=Θ(n22n)T(n) = \Theta(n^2 2^n)

  2. B.

    T(n)=Θ(n2n)T(n) = \Theta(n 2^n)

  3. C.

    T(n)=Θ((log⁡n)22n)T(n) = \Theta((\log n)^2 2^n)

  4. D.

    T(n)=Θ(4n)T(n) = \Theta(4^n)

Attempted by 128 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…