<s>[INST] Solve the recurrence relation:$ T(n) = \sqrt{n} T \left(\sqrt n \right) + n$ $$T(n) = \sqrt{n} T \left(\sqrt n \right) + n$$
Master method does not apply here. Recursion tree goes a long way. Iteration method would be preferable.
The answer is $Θ (n \log \log n)$.
Can anyone arrive at the solution.
 [/INST] Yes, the Master Theorem can be applied. Here's how:
$$T(n) = \sqrt{n} T(\sqrt{n}) + n = \sqrt{n} T(\sqrt{n}) + \mathcal{O}(n)$$
Let $n = 2^k$, $\sqrt{n} = 2^{k/2}$, and $k = \log{n}$. Substituting in above equation, we get:
$$T(2^k) = 2^{k/2} T(2^{k/2}) + 2^k \tag{1}$$
Dividing (1) by $2^k$, we get:
$$\frac{T(2^k)}{2^k} = \frac{2^{k/2}T(2^{k/2})}{2^k} + 1\tag{2}$$
Simpliifying $\frac{2^{k/2}}{2^k} = \frac{1}{2^{k/2}}$ in $(2)$ gives us:
$$\frac{T(2^k)}{2^k} = \frac{T(2^{k/2})}{2^{k/2}} + 1\tag{3}$$
Let $y(k) = \frac{T(2^k)}{2^k}$, then $(3)$ gives us:
$$y(k) = y\left(\frac{k}{2}\right) + 1\tag{4}$$
Now, we apply the Master Theorem ($T(n) = aT\left(\frac{n}{b}\right) + n^d$), where $a=1, b=2$, and $d=0$, $a=b^d = 1$.
Because $d=0$, we have:
$$y(k) = k^d\log{k} = \log{k}\tag{5}$$
But, we also know that $T(2^k) = 2^ky(k)$, then
$$T(2^k) = 2^k\log{k} \implies T(n) = n\log{\log{n}}$$
since $n=2^k$ and $k = \log{n}$.
Finally: $T(n) = \Theta(n\log{\log{n}})$
</s>