$$T(n) = \sqrt{n} T \left(\sqrt n \right) + n, n>1$$ $$T(n) = k, n\le1$$
My book says for upper bound to simplify to
$$T(n) \le \sqrt{n}c\sqrt n\log\left(\sqrt n\right) + n$$ $$ = nc\log\left(\sqrt n\right) + n$$ $$ = \frac{1}{2}nc\log\left( n\right) + n$$ $$ \le cn\log\left(n\right)$$
A few questions here: how does $T(\sqrt n)$ simplify to $c\sqrt n\log\left(\sqrt n\right)$?
Or maybe I'm just asking: How do we know for sure that $T(\sqrt n)\le c\sqrt n\log\left(\sqrt n\right)$?
Also, how does $\frac{1}{2}nc\log\left( n\right) + n$ simplify to $ cn\log\left(n\right)$?
By the way, the book says that it assumes that $1\le\frac{1}{2}c\log{(n)}$.
We can use the change of variable $a_n=T(2^n)$ to get the recursion $$ a_n=2^{n\over2}a_{n\over2}+2^n=2^{{n\over2}+{n\over2^2}}a_{n\over2^2}+2\times2^{n}=2^{{n\over2}+{n\over2^2}+{n\over2^3}}a_{n\over2^3}+3\times2^n =\cdots=2^{n(1-{1\over2^m})}a_{n\over2^m}+m2^n\\ \implies a_{2^m}=2^{2^m-1}a_1+m2^{2^m}\implies a_m=a_{2^{\log_2m}}=2^{m-1}a_1+2^m\log_2m\\ \implies T(m)=a_{\log_2m}={ma_1\over2}+m\log_2\log_2m $$
So a solution to the given recurrence is ($\alpha$ is a constant which equals $T(2)/2$) $$ T(n)=\alpha n+n\log_2\log_2n $$ which falls apart at $n\le1$ as pointed out in the comments. Suppose $n\ge2$. Then $\alpha n\le \alpha n\log_2 n$ and $n\log_2\log_2n\le n\log_2n$. Letting $c=1+\alpha$ we have $$ T(n)\le cn\log_2n $$