GATE 2026 CS1 Q.17: solution and answer

GATE 2026 · CS1Q.17 · 1 mark · MCQ

Consider the following recurrence relations:

For all $n > 1$ ,
$T_{1} (n) = 4 T_{1} (\frac{n}{2}) + T_{2} (n)$
$T_{2} (n) = 5 T_{2} (\frac{n}{4}) + Θ (lo g_{2} n)$

Assume that for all $n \leq 1$ , $T_{1} (n) = 1$ and $T_{2} (n) = 1$ .

Which one of the following options is correct?

(A)
$T_{1} (n) = Θ (n^{2})$
(B)
$T_{1} (n) = Θ (n^{2} lo g_{2} n)$
(C)
$T_{1} (n) = Θ (n^{l o g_{4} 5})$
(D)
$T_{1} (n) = Θ (n^{l o g_{4} 5} lo g_{2} n)$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

T1(n) = Θ(n²), matching option (A)

Official answer: ASource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

Solve the inner recurrence T2(n) = 5T2(n/4) + Θ(log₂n) via the Master theorem: a=5, b=4, so the watershed function is n^{log_4 5} ≈ n^{1.161}.
Since f(n) = Θ(log₂n) = O(n^{log_4 5 - ε}) for ε = 1 > 0, Master theorem Case 1 applies, giving T2(n) = Θ(n^{log_4 5}).
Substitute this closed form into the outer recurrence: T1(n) = 4T1(n/2) + Θ(n^{log_4 5}).
Apply the Master theorem to T1: a=4, b=2, so the watershed function is n^{log_2 4} = n².
Compare f(n) = Θ(n^{log_4 5}) ≈ Θ(n^{1.161}) with n²: since log_4 5 < 2, f(n) = O(n^{2-ε}) for ε = 2 - log_4 5 > 0, so Master theorem Case 1 applies again.
Therefore T1(n) = Θ(n²), which is option (A).

KEY IDEA

Solve the inner recurrence T2 first with the Master theorem, then substitute the resulting Θ-bound into the outer recurrence T1 and apply the Master theorem a second time.

WATCH OUT FOR

Applying the Master theorem to T1 using the printed f(n) = T2(n) symbolically (or assuming T2(n) = Θ(n) / Θ(log n) without first solving it), instead of substituting the actual closed form Θ(n^{log_4 5}) for T2(n) before comparing against n^{log_2 4} = n².

From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 14 Complexity questions, with notes

GATE 2026 CS1 Q.17: solution and answer

Answer and solution

More Complexity questions