Home › Previous year questions › GATE 2024 CS (CS2) › Question 15GATE 2024 CS (CS2) – Question 15 Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice
Let $T(n)$ be the recurrence relation defined as follows: $T(0)=1$, $T(1)=2$, and $T(n)=5T(n-1)-6T(n-2)$ for $n\ge 2$. Which one of the following statements is TRUE?
$T(n)=\Theta(2^n)$ $T(n)=\Theta(n2^n)$ $T(n)=\Theta(3^n)$ $T(n)=\Theta(n3^n)$ Practise this question in The GATE Grind →
Show answer and explanation Correct answer: (A) $T(n)=\Theta(2^n)$
Explanation Characteristic roots are 2 and 3. T(n)=A·2^n+B·3^n; T(0)=1, T(1)=2 gives A+B=1 and 2A+3B=2, so B=0 and A=1. Hence T(n)=2^n.
More Asymptotic Analysis and Time/Space Complexity questions GATE 2023 CS Q29 – Let f and g be functions of natural numbers given by f(n) = n and g(n) = n2. Which of the… GATE 2023 CS Q54 – Consider functions Function 1 and Function 2 expressed in pseudocode as follows: Let f… GATE 2022 CS Q11 – Which one of the following statements is TRUE for all positive functions f(n)? GATE 2022 CS Q51 – Consider the following recurrence: f(1)=1; f(2n)=2f(n)-1, for n1; f(2n+1)=2f(n)+1, for n1.… GATE 2021 CS (CS1) Q13 – Consider the following three functions. f 1 = 10n, f 2 = n n, f 3 = nn Which one of the… GATE 2021 CS (CS1) Q40 – Consider the following recurrence relation. T(n) = T(n/2) + T(2n/5) + 7n if n>0; T(n)=1 if… All Asymptotic Analysis and Time/Space Complexity questions →