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

PYQ GATE 2025

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 153 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…