The GATE Grind

GATE 2024 CS (CS1) – Question 42

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

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?

  1. $T(n)=\Theta(n\log\log n)$
  2. $T(n)=\Theta(n\log n)$
  3. $T(n)=\Theta(n^2\log n)$
  4. $T(n)=\Theta(n^2\log\log n)$

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

All Asymptotic Analysis and Time/Space Complexity questions →