Success TrackerSuccess Tracker
Log inSign up

GATE CS 2024 Set 2 — Question 15

MCQ+1 / -0.33MediumRecurrence RelationsSets & CombinatoricsEngineering Mathematics

Engineering Mathematics → Sets & Combinatorics → Recurrence Relations

Last updated

Question

Let T(n)T(n) be the recurrence relation defined as follows:T(0)=1T(0) = 1,
T(1)=2T(1) = 2, and
T(n)=5T(n−1)−6T(n−2)T(n) = 5T(n - 1) - 6T(n - 2) for n≥2n \geq 2.
Which one of the following statements is TRUE?
A.
T(n)=Θ(2n)T(n) = \Theta(2^n)
B.
T(n)=Θ(n2n)T(n) = \Theta(n2^n)
C.
T(n)=Θ(3n)T(n) = \Theta(3^n)
D.
T(n)=Θ(n3n)T(n) = \Theta(n3^n)

Correct answer

(A) T(n) = Θ(2ⁿ)

Solution

The given recurrence relation is a linear homogeneous recurrence relation with constant coefficients: T(n)=5T(n−1)−6T(n−2)T(n) = 5T(n - 1) - 6T(n - 2).
1.Find the characteristic equation:
The characteristic equation is r2−5r+6=0r^2 - 5r + 6 = 0.
2.Solve for the roots:
(r−2)(r−3)=0⇒r1=2,r2=3(r - 2)(r - 3) = 0 \Rightarrow r_1 = 2, r_2 = 3.
3.Write the general solution:
T(n)=c1(2n)+c2(3n)T(n) = c_1(2^n) + c_2(3^n).
4.Use initial conditions to find constants:
  • For n=0n = 0: T(0)=c1(20)+c2(30)=c1+c2=1T(0) = c_1(2^0) + c_2(3^0) = c_1 + c_2 = 1
  • For n=1n = 1: T(1)=c1(21)+c2(31)=2c1+3c2=2T(1) = c_1(2^1) + c_2(3^1) = 2c_1 + 3c_2 = 2
Solving the system:
From the first equation, c1=1−c2c_1 = 1 - c_2.
Substitute into the second: 2(1−c2)+3c2=2⇒2−2c2+3c2=2⇒c2=02(1 - c_2) + 3c_2 = 2 \Rightarrow 2 - 2c_2 + 3c_2 = 2 \Rightarrow c_2 = 0.
Then c1=1−0=1c_1 = 1 - 0 = 1.
5.Final expression for T(n)T(n):
T(n)=1⋅2n+0⋅3n=2nT(n) = 1 \cdot 2^n + 0 \cdot 3^n = 2^n.
6.Determine asymptotic complexity:
Since T(n)=2nT(n) = 2^n, it follows that T(n)=Θ(2n)T(n) = \Theta(2^n).
Thus, option (A) is correct.

More questions on Sets & Combinatorics

2024 Set 2 Q3In an engineering college of 10,000 students, 1,500 like neither their core branches nor other…2024 Set 1 Q11Let f:R→Rf: \mathbb{R} \rightarrow \mathbb{R} be a function such that…2024 Set 2 Q12Let pp and qq be the following propositions: pp: Fail grade can be given. qq: Student scores…2024 Set 1 Q12The product of all eigenvalues of the matrix…2024 Set 1 Q14Consider a permutation sampled uniformly at random from the set of all permutations of…

Practice GATE CS PYQs with adaptive difficulty

Timed practice, skill tracking, and AI explanations — free to start.

Start practicing free