Let 𝑇(𝑛) be the recurrence relation defined as follows:
        𝑇(0) = 1,
        𝑇(1) = 2, and
        𝑇(𝑛) = 5𝑇(𝑛 − 1) − 6𝑇(𝑛 − 2) for 𝑛 ≥ 2
Which one of the following statements is TRUE?

Question

Let 𝑇(𝑛) be the recurrence relation defined as follows:

𝑇(0) = 1,

𝑇(1) = 2, and

𝑇(𝑛) = 5𝑇(𝑛 − 1) − 6𝑇(𝑛 − 2) for 𝑛 ≥ 2

Which one of the following statements is TRUE?

Accepted Answer

Correct answer: A — Key idea: solve the recurrence by the characteristic equation. Form the characteristic equation: r^2 - 5r + 6 = 0, which has roots r = 2 and r = 3. Write the general solution: T(n) = A·2^n + B·3^n. Use initial conditions: T(0)=1 ⇒ A + B = 1; T(1)=2 ⇒ 2A + 3B = 2. Solve the system: subtracting 2×(A + B = 1) from (2A + 3B = 2) gives B = 0, so A = 1. Therefore T(n) = 2^n exactly, so T(n) = Θ(2^n). Conclusion: the recurrence solves to T(n) = 2^n, hence the correct growth is Θ(2^n).

Answer

A. 𝑇(𝑛) = Θ(2𝑛 )

Answer

B. 𝑇(𝑛) = Θ(𝑛2𝑛 )

Answer

C. 𝑇(𝑛) = Θ(3𝑛)

Answer

D. 𝑇(𝑛) = Θ(𝑛3𝑛)

Let 𝑇(𝑛) be the recurrence relation defined as follows: 𝑇(0) = 1, 𝑇(1) =…