Consider the following recurrence relation: $$T(n) = \begin{cases} \sqrt{n} T(\sqrt{n}) + n & \text{for } n \ge 1, \\ 1 & \text{for } n = 1. \end{cases}$$ Which one of the following options is CORRECT?

Given the recurrence relation for $n > 1$:

Divide both sides by $n$:

Define $S(n) = \frac{T(n)}{n}$. The recurrence simplifies to:

To solve this, let $n = 2^m$, so $\sqrt{n} = 2^{m/2}$ and $m = \log_2 n$:

Let $G(m) = S(2^m)$. Then:

By the Master Theorem (Case 2 with $a=1, b=2, k=0$):

Substitute back $m = \log_2 n$:

Since $T(n) = n \cdot S(n)$:

Hence, (A) is the correct option.