Algorithm runnning time $T(n) = \sqrt{n} \cdot T(\sqrt{n}) + \sqrt{n} $ using substitution I need to solve the following recurrence, only using the substituion method (CLRS):
$$ T(n) = \sqrt n \cdot T(\sqrt n) + \sqrt n $$
This is what I have done so far:


*

*Changing variables
$$ m = \log_{2}n$$
$$ n = 2^{m} $$
$$ \log n = m $$

*Updating the recurrence function, so that $T(2^{m}) = S(m)$
$$ T(2^{m}) = 2^\frac{m}{2} \cdot T(2^\frac{m}{2}) + 2^\frac{m}{2}$$
$$ S(m) = \frac{m}{2} \cdot T(\frac{m}{2}) + \frac{m}{2}$$
And then here, I'm not sure how to proceed nor if my argument is correct so far.
I tried to follow a similar example answered here, but I wasn't able to properly translate it.
 A: Go a little further with $n = 2^{2^m}$.
Since $\sqrt{2^{2^m}} = 2^{2^{m-1}}$, this becomes
$T(2^{2^m}) = 2^{2^{m-1}}T(2^{2^{m-1}})+2^{2^{m-1}}$.
Letting $T(2^{2^m}) = s(m)$, this becomes
$s(m) = 2^{2^{m-1}}s(m-1)+2^{2^{m-1}}$.
Dividing by $2^{2^{m}}$ this is
$\frac{s(m)}{2^{2^{m}}} = \frac{s(m-1)}{2^{2^{m-1}}}+\frac{1}{2^{2^{m-1}}}$.
Letting $u(m) = \frac{s(m)}{2^{2^{m}}}$, this becomes
$u(m) = u(m-1)+ \frac{1}{2^{2^{m-1}}}$.
$u(m)$ converges to a constant $c$, so
$s(m) \to c2^{2^{m}}$ so
$T(2^{2^m})  \to c2^{2^{m}}$
or $T(n) \to cn$.
Putting this into the original equation, we get
$cn = \sqrt{n}c\sqrt{n}+\sqrt{n}$
which is approximately true.
To get a more accurate answer, let 
$T(n) = c n+r(n)$ 
and see what you can find about
$r(n)$.
A: Hint.
Using another approach, intending to obtain a comparison result, with
$$
\mathcal{T}(\cdot) = T\left(4^{(\cdot)}\right), z = \log_4 n,\ \ \mathbb{T}(\cdot) = \mathcal{T}\left(2^{(\cdot)}\right),\ u = \log_2 z
$$
we obtain the recurrence
$$
\mathbb{T}(u)=2^{2^u}\mathbb{T}(u-1)+2^{2^u}
$$
with solution
$$
\mathbb{T}(u)= 4^{2^u}C_0+4^{2^u}\sum_{k=0}^{u-1}4^{-2^k}
$$
After returning to $T(n)$ we have
$$
T(n) = n C_0 + n\sum_{k=0}^{\log_2(\log_4 n)-1}4^{-2^k}
$$
