GATE CS 2024 Set 1 — Question 42

The given recurrence relation is:$$T(n) = \sqrt{n} T(\sqrt{n}) + n$$To solve this, we can use the substitution method.
Let $n = 2^m$, which implies $m = \log_2 n$. Then $\sqrt{n} = 2^{m/2}$.
Substituting these into the recurrence:$$T(2^m) = 2^{m/2} T(2^{m/2}) + 2^m$$Divide the entire equation by $2^m$:$$\frac{T(2^m)}{2^m} = \frac{2^{m/2} T(2^{m/2})}{2^m} + 1$$$$\frac{T(2^m)}{2^m} = \frac{T(2^{m/2})}{2^{m/2}} + 1$$Let $S(m) = \frac{T(2^m)}{2^m}$. The recurrence becomes:$$S(m) = S(m/2) + 1$$This is a standard recurrence relation (similar to binary search complexity) whose solution is:$$S(m) = \Theta(\log m)$$Now, substitute back $S(m) = \frac{T(n)}{n}$ and $m = \log_2 n$:$$\frac{T(n)}{n} = \Theta(\log(\log_2 n))$$$$T(n) = n \cdot \Theta(\log \log n)$$$$T(n) = \Theta(n \log \log n)$$Thus, option (A) is correct.