GATE CSE 2026 | Set 1 | Question: 7

Question

Consider the following recurrence relations:

For all $n>1$,
\[
\begin{array}{c}
T_{1}(n)=4 T_{1}\left(\frac{n}{2}\right)+T_{2}(n) \\
T_{2}(n)=5 T_{2}\left(\frac{n}{4}\right)+\Theta\left(\log _{2} n\right)
\end{array}
\]
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)=\Theta\left(n^{2}\right)$
• B. $T_{1}(n)=\Theta\left(n^{2} \log _{2} n\right)$
• C. $T_{1}(n)=\Theta\left(n^{\log _{4} 5}\right)$
• D. $T_{1}(n)=\Theta\left(n^{\log _{4} 5} \log _{2} n\right)$

Comments

Done ✅

---

we can solve using tree substitution but from master theorm , we can easily solve it

Answer 1

We can see that equation of T1 has T2 in it.

 

 so first lets calculate T2.

 

(you will understand only if you know basics to use masters theorem).

 

Answer 2

Here is the explanation

 

Answer 3

Here is the Explanation 

 

Answer 4

 

Answer 5

.

 

Answer 6

first option is correct