Consider the following recurrence relations: For all n > 1: T 1(n) = 4T 1(n/2) + T 2(n) T 2(n) = 5T 2(n/4) + ( 2 n) Assume that for all n 1, T 1(n) = (1) and T 2(n) = (1). Which one of the following options is correct?

$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)$

GATE 2026 CS (CS1) – Question 17

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

Consider the following recurrence relations:
For all $n > 1$:
$$T_1(n) = 4T_1(n/2) + T_2(n)$$
$$T_2(n) = 5T_2(n/4) + \Theta(\log_2 n)$$
Assume that for all $n \le 1$, $T_1(n) = \Theta(1)$ and $T_2(n) = \Theta(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)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $T_1(n) = \Theta(n^2)$

Explanation

First, analyze the recurrence for $T_2(n)$:
$$T_2(n) = 5T_2(n/4) + \Theta(\log_2 n)$$
Using the Master Theorem $T(n) = aT(n/b) + f(n)$:
- $a = 5, b = 4$
- $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})$, Case 1 of the Master Theorem applies:
$$T_2(n) = \Theta(n^{\log_4 5})$$

Now substitute $T_2(n)$ into the recurrence for $T_1(n)$:
$$T_1(n) = 4T_1(n/2) + \Theta(n^{\log_4 5})$$
Apply the Master Theorem to $T_1(n)$:
- $a = 4, b = 2$
- $n^{\log_b a} = n^{\log_2 4} = n^2$
- Compare $n^{\log_b a} = n^2$ with $f(n) = n^{\log_4 5} \approx n^{1.161}$.
- Since $2 > \log_4 5$, $f(n) = O(n^{2 - \epsilon})$ for $\epsilon = 2 - \log_4 5 > 0$.
- Therefore, Case 1 of the Master Theorem applies again:
$$T_1(n) = \Theta(n^2)$$

Thus, option (A) is correct.