GATE CS 2024 Set 1 Q32 — Asymptotic Worst Case Time and Space Complexity

To solve the recurrence relation $T(n) = \sqrt{n} T(\sqrt{n}) + n$, we can simplify it by dividing both sides by $n$:

$$\frac{T(n)}{n} = \frac{\sqrt{n} T(\sqrt{n})}{n} + 1 = \frac{T(\sqrt{n})}{\sqrt{n}} + 1$$

Let $S(n) = \frac{T(n)}{n}$. Substituting this into the equation gives:

$$S(n) = S(\sqrt{n}) + 1$$

Now, we apply a change of variables. Let $n = 2^m$, which means $\sqrt{n} = 2^{m/2}$. Substituting these into the recurrence:

$$S(2^m) = S(2^{m/2}) + 1$$

Letting $R(m) = S(2^m)$, we get the standard recurrence:

$$R(m) = R(m/2) + 1$$

Using the Master Theorem, the solution to this recurrence is:

$$R(m) = \Theta(\log m)$$

Substituting back $m = \log n$ and $S(n) = R(m)$:

$$S(n) = \Theta(\log \log n)$$

Finally, since $T(n) = n \cdot S(n)$:

$$T(n) = \Theta(n \log \log n)$$

Thus, the correct option is A.