Register

GATE CSE 2026 | Set 1 | Algorithms | Memory Based | Question 34

• retagged by
551 views
5 5 votes

Consider the following:
For all $n>1$

$$
\begin{aligned}
& T_1(n)=4 T_1(n / 2)+T_2(n) \\\\
& T_2(n)=5 T_2(n / 4)+\theta\left(\log _2 n\right)
\end{aligned}
$$


Assume that for all $n \leq 1$

$$
T_1(n)=1 \text { and } T_2(n)=1
$$


Which of the following option is correct

  1. $T_1(n)=\theta\left(n^2 \log _2 n\right)$
     
  2. $T_1(n)=\theta\left(n^2\right)$
     
  3. $T_1(n)=\theta\left(n^{\log _4 5} \log _2 n\right)$
     
  4. $T_1(n)=\theta\left(n^{\log _4 5}\right)$

2 Answers

1 1 vote

First one would be n2 , that is option B;

Second one would be log5-base4, which is option D;

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2026 | Set ...Next → · GATE CSE 2026 | Set ...
← Previous in category · GATE CSE 2026 | Set ...Next in category → · GATE CSE 2026 | Set ...
Position:
Show:

Related questions

1 1 vote
1 1 answer
474
474 views
GO Classes asked Feb 12
474 views
GATE CSE 2026 | Set 1 | Algorithms | Memory Based | Question 38
Suppose the input directed graph $G(V,E)$ is a DAG. For an edge $(u,v)\in E$, which of the following will NEVER be correct in DFS discovery/finish times?$d[u] < d[v] < f[...
2 2 votes
1 1 answer
660
660 views
GO Classes asked Feb 12
660 views
GATE CSE 2026 | Set 1 | Algorithms | Memory Based | Question 36
If there is no path from $\delta$ to a of length at most k , then $d_k(u)=\infty$Statement 1: For every $u \geq 0$ and $u \in V, d_{k+1}(u) \leq d_k(u)$.Statement 2: For ...
0 0 votes
1 1 answer
471
471 views
GO Classes asked Feb 12
471 views
GATE CSE 2026 | Set 1 | Algorithms | Memory Based | Question 33
Let $\mathrm{G}(\mathrm{V}, \mathrm{E})$ be a simple, undirected, edge-weighted graph with unique edge weights.Which of the following statements about MST (minimum spanni...
5 5 votes
4 4 answers
1.1k
1.1k views
NullPointer_Pro asked Dec 24, 2025
1,124 views
GATE CS Practice : The "Master Theorem" (Algorithms)
Consider the following recurrence relation describing the running time of an algorithm: $$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$$$(Base\ condition: T(1) =...