Q5

MCQ1 mark, −0.33

Let $\text{T(n)}$ be the recurrence relation defined as follows:

\begin{array}{l} T(0)=1, \\ T(1)=2, \text { and } \\ T(n)=5 T(n-1)-6 T(n-2) \text { for } n \geq 2 \end{array}

Which one of the following statements is TRUE?

(A)

$T(n)=\Theta\left(2^{n}\right)$

(B)

$T(n)=\Theta\left(n 2^{n}\right)$

(C)

$T(n)=\Theta\left(3^{n}\right)$

(D)

$T(n)=\Theta\left(n 3^{n}\right)$

Loading…