GATE CS 2024 Set 2 Q5 — Asymptotic Worst Case Time and Space Complexity

The given recurrence relation is a second-order linear homogeneous recurrence relation with constant coefficients:

Step 1: Find the Characteristic Equation

The characteristic equation associated with this recurrence is:

Factoring the quadratic equation:

Thus, the characteristic roots are $r_1 = 2$ and $r_2 = 3$.

Step 2: Formulate the General Solution

Since the roots are distinct, the general solution is of the form:

Step 3: Solve for Constants using Initial Conditions

We are given the initial conditions $T(0) = 1$ and $T(1) = 2$. Substituting these into the general solution:

1. For $n = 0$: $$T(0) = c_1 2^0 + c_2 3^0 \implies c_1 + c_2 = 1 \quad \text{--- (Equation 1)}$$
2. For $n = 1$: $$T(1) = c_1 2^1 + c_2 3^1 \implies 2c_1 + 3c_2 = 2 \quad \text{--- (Equation 2)}$$

From Equation 1, we have $c_1 = 1 - c_2$. Substituting this into Equation 2:

Substituting $c_2 = 0$ back into Equation 1 gives:

Step 4: Determine the Asymptotic Complexity

Substituting the values of $c_1$ and $c_2$ back into the general solution:

Therefore, the asymptotic tight bound is:

Hence, Option A is the correct statement.