GATE 2024 CS (CS1) – Question 42
Consider the recurrence $T(n)=\sqrt{n}\,T(\sqrt{n})+n$ for $n\ge 1$... with $T(1)=1$. Which one of the following options is CORRECT?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $T(n)=\Theta(n\log\log n)$
Explanation
**1. Remove the multiplicative n growth.** Put $T(n)=nS(n)$. Since $T(\sqrt n)=\sqrt n\,S(\sqrt n)$, substitution gives $nS(n)=nS(\sqrt n)+n$, hence $S(n)=S(\sqrt n)+1$.
**2. Count the recursion depth.** After j steps the argument is $n^{1/2^j}$. It reaches a fixed constant greater than 1 when $2^j$ is proportional to ln n, so $j=\Theta(\log\log n)$. Each level adds 1 to S.
**3. Restore the factor n.** $S(n)=\Theta(\log\log n)$, giving $T(n)=\Theta(n\log\log n)$. **Answer: A.** As usual, the asymptotic recurrence stops at a constant-size base case; repeated real square roots do not literally reach 1 in finitely many steps.
More Asymptotic Analysis and Time/Space Complexity questions
- GATE 2024 CS (CS2) Q15
- GATE 2023 CS Q29
- GATE 2023 CS Q54
- GATE 2022 CS Q11
- GATE 2022 CS Q51
- GATE 2021 CS (CS1) Q13
All Asymptotic Analysis and Time/Space Complexity questions →