Exams › GATE › Engineering Mathematics

Consider the following recurrence relation: T(n) = 2T(n − 1) + n2ⁿ for n > 0, T(0) = 1. Which ONE of the following options is CORRECT?

1. T(n) = Θ(n² 2ⁿ)
2. T(n) = Θ(n 2ⁿ)
3. T(n) = Θ((log n)² 2ⁿ)
4. T(n) = Θ(4ⁿ)

Correct answer: T(n) = Θ(n² 2ⁿ)

Solution

Let S(n)=T(n)/2^n. Dividing T(n)=2T(n-1)+n*2^n by 2^n gives S(n)=S(n-1)+n, so S(n)=Theta(n^2). Therefore T(n)=Theta(n^2 * 2^n), which is the first option, not Theta(4^n).

Related GATE Engineering Mathematics questions

• The second-order differential equation in an unknown function u: u(x,y) is defined as ∂²u/∂x² = 2. Assuming g: g(x), f: f(y), and h: h(y), the general solution of the above differential equation is
• Which of the following equations belong/belongs to the class of second-order, linear, homogeneous partial differential equations:
• The solution of the equation x dy/dx + y = 0 passing through the point (1,1) is
• The Laplace transform F(s) of the exponential function, f(t)=e^(at) when t≥0, where a is a constant and (s−a)>0, is
• The Laplace transform of sinh(at) is
• An ordinary differential equation is given below. (dy/dx)(x ln x) = y The solution for the above equation is (Note: K denotes a constant in the options)

⚔️ Practice GATE Engineering Mathematics free + battle 1v1 →