Algorithm runnning time $T(n) = \sqrt{n} \cdot T(\sqrt{n}) + \sqrt{n} $ using substitution

Question

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:

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

2. 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.

Answer 1

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)$.

Answer 2

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} $$