GATE CS 2026 Set 1 Q.17: Asymptotic Analysis and Time/Space Complexity

Consider the following recurrence relations:

For all $n > 1$ ,

T_1(n) = 4T_1\left(\frac{n}{2}\right) + T_2(n)

T_2(n) = 5T_2\left(\frac{n}{4}\right) + \Theta(\log_2 n)

Assume that for all $n \le 1$ , $T_1(n) = 1$ and $T_2(n) = 1$ .

Which one of the following options is correct?

$T_1(n) = \Theta(n^2)$

$T_1(n) = \Theta(n^2 \log_2 n)$

$T_1(n) = \Theta(n^{\log_4 5})$

$T_1(n) = \Theta(n^{\log_4 5} \log_2 n)$

Official answer and solution

Solution

Solve $T_2(n)$ first using the Master Theorem, then substitute the asymptotic bound for $T_2(n)$ into the recurrence for $T_1(n)$ .

Solve $T_2(n) = 5T_2(n/4) + \Theta(\log_2 n)$ :
- Here $a = 5, b = 4$ , so $n^{\log_b a} = n^{\log_4 5} \approx n^{1.161}$ .
- Since $f(n) = \Theta(\log_2 n) = O(n^{\log_4 5 - \epsilon})$ for $\epsilon = 0.1$ , Case 1 of the Master Theorem gives: $T_2(n) = \Theta\left(n^{\log_4 5}\right)$
Solve $T_1(n) = 4T_1(n/2) + T_2(n)$ :
- Here $a = 4, b = 2$ , so $n^{\log_b a} = n^{\log_2 4} = n^2$ .
- Since $T_2(n) = \Theta(n^{\log_4 5})$ and $\log_4 5 = \frac{\log_2 5}{2} < \frac{4}{2} = 2$ , we have $T_2(n) = O(n^{2 - \epsilon})$ for $\epsilon = 2 - \log_4 5 > 0$ .
- By Case 1 of the Master Theorem, $T_1(n) = \Theta(n^2)$ .

Final answer

Option (A)

Common trap

Assuming $T_2(n)$ dominates $n^2$ without checking that $\log_4 5 \approx 1.161 < 2$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 17 of 65
Section: Computer Science and Information Technology

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.