GATE CS 2026 Set 1 Q7 — Asymptotic Worst Case Time and Space Complexity

To find the asymptotic complexity of $T_1(n)$, we solve the recurrence relations step-by-step using the Master Theorem.

Step 1: Solve for $T_2(n)$

The recurrence relation for $T_2(n)$ is given by:

Comparing this with the standard Master Theorem form $T(n) = a T(n/b) + f(n)$:

• $a = 5$
• $b = 4$
• $f(n) = \Theta(\log_2 n)$

We compare $f(n)$ with $n^{\log_b a}$:

Since $f(n) = \Theta(\log_2 n) = O(n^{\log_4 5 - \epsilon})$ for any $0 < \epsilon < 0.16$, this falls under Case 1 of the Master Theorem. Therefore:

Step 2: Solve for $T_1(n)$

Now, substitute the asymptotic behavior of $T_2(n)$ into the recurrence relation for $T_1(n)$:

Comparing this with the Master Theorem form:

• $a = 4$
• $b = 2$
• $f(n) = \Theta\left(n^{\log_4 5}\right)$

We compare $f(n)$ with $n^{\log_b a}$:

Since $\log_4 5 \approx 1.16 < 2$, we have:

This also falls under Case 1 of the Master Theorem. Therefore:

Thus, the correct option is A.