Skip to content
GATEiit

GATE CSE 2026 Session 1 Q17: Solve nested recurrences T1 = 4T1(n/2) + T2, T2 = 5T2(n/4) + log n

Question

Consider the following recurrence relations:

For all n>1n > 1,

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

T2(n)=5T2(n4)+Θ(log⁡2n)T_2(n) = 5T_2\left(\frac{n}{4}\right) + \Theta(\log_2 n)

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

Which one of the following options is correct?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: A (official GATE 2026 final answer key)

Concept used: Master theorem applied twice: solve the inner recurrence, then use it as the driving term of the outer one.

First step: For T2T_2: nlog⁡45≈n1.16n^{\log_4 5} \approx n^{1.16} dominates log⁡n\log n, so T2(n)=Θ(nlog⁡45)T_2(n) = \Theta(n^{\log_4 5}); compare that with nlog⁡24=n2n^{\log_2 4} = n^2.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 1 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2026 Session 1 questions →