Guess on big-O of recurrence relation $\sqrt{n}\cdot T(\sqrt{n})+\sqrt{n}$ I have to make a guess on Big-O of the recurrence relation: $$T(N)=\sqrt{n}\cdot T(\sqrt{n})+\sqrt{n}$$
I have used change of variables where I did:
$n=2^m$
$$T(2^m)=2^{m/2}\cdot T(2^{m/2})+2^{m/2}$$
And then $S(m)=T(2^m)$. The first 4 levels are then:
$$S(m)=2^{m/2}\cdot S(m/2)+2^{m/2}$$
$$S(m/2)=2^{m/4}\cdot S(m/4)+2^{m/4}$$
$$S(m/4)=2^{m/8}\cdot S(m/8)+2^{m/8}$$
$$S(m/8)=2^{m/16}\cdot S(m/16)+2^{m/16}$$
Then I solved it and got change from 1 level to 2:
$$S(m/2)=2^{m/4}\cdot (2^{m/8}\cdot S(m/8)+2^{m/8})+2^{m/4}$$
$$S(m/2)=2^{m/4}\cdot 2^{m/8}\cdot S(m/8)+2^{3m/8}+2^{m/4}$$
Level 3:
$$S(m)=2^{m/2}\cdot 2^{m/4}\cdot 2^{m/8}\cdot S(m/8)+2^{7m/8}+2^{3m/4}+2^{m/2}$$
I can see that each level is multiplied by $2^{m/2^i}$ and we add $2^{\frac{2^i-1}{2^i}m}$.
Therefore I could write it like:
$$S(m)=2^{\frac{m}{2}\cdot(1+(1/2)+(1/4)+(1/8)+...+(\frac{1}{2^{i-1}}))}+[2^{\frac{m}{2}}+2^{\frac{3m}{4}}+2^{\frac{7m}{8}}+...+2^{\frac{2^i-1}{2^i}m}]$$
And here is where I'm stuck.. I see that the first part of equations is going towards $2^m$, but what about the square parenthesis?
 A: As for $n > 0$
$$
\frac{T(n)}{n} = \frac{\sqrt{n}T\left(\sqrt{n}\right)}{n}+\frac{\sqrt{n}}{n}
$$
calling $R(n) = \frac{T(n)}{n}$ we follow with
$$
R(n)=R\left(\sqrt{n}\right)+\frac{1}{\sqrt{n}}
$$
or
$$
R\left(2^{\log_2 n}\right) = R\left(2^{\log_2 \sqrt{n}}\right)+\frac{1}{\sqrt{n}}
$$
now calling $\mathcal{R}\left(\cdot\right) = R\left(2^{(\cdot)}\right)$ and $z = \log_2 n$ we follow with
$$
\mathcal{R}\left(z\right) = \mathcal{R}\left(\frac z2\right) +2^{-\frac z2} 
$$
now making the transformation $\mathbb{R}(\cdot) = \mathcal{R}\left(2^{(\cdot)}\right)$ and $u = \log_2 z$ we follow with the recurrence
$$
\mathbb{R}(u) = \mathbb{R}(u-1) + 2^{-2^{u-1}}
$$
with solution
$$
\mathbb{R}(u) = c_0+\sum_{k=0}^{u-1}2^{-2^k}
$$
and now going backwards with $z=2^u$ and $n = 2^z$ we arrive at
$$
R(n) = c_0+\sum_{k=0}^{\log_2(\log_2 n)-1}2^{-2^k}
$$
and finally
$$
T(n) = n\left(c_0+n^{-\frac 12}+n^{-\frac{1}{2^2}}+\cdots +n^{-\frac{1}{2^k}}\right)
$$
NOTE
$$
2^{-2^{\log_2(\log_2 n)-1}} = n^{-\frac 12}
$$
A: First of all, the equation only links elements in the set $\{a^{2^n}|n\in\mathbb{Z}\}$. These sets are disjoint, and there is no relation between the sets.
Since you're looking at $T(x)$ for arbitrarily large values of $x$, let's assume $a>1$.
Second, let's investigate $\dfrac{T(a^{2^n})}{a^{2^n}}=r_n$.
If $T(a^{2^n})=r_n a^{2^n}$, then $T(a^{2^{n+1}})=a^{2^{n}}\times T(a^{2^{n}})+a^{2^n}=a^{2^n}(r_n a^{2^n}+1)$.
Therefore, $r_{n+1}=\dfrac{T(a^{2^{n+1}})}{a^{2^{n+1}}}=\dfrac{a^{2^n}(r_n a^{2^n}+1)}{a^{2^{n+1}}}=r_n+\dfrac{1}{a^{2^n}}$
Obviously then, $r_n=r_0+\displaystyle\sum_{k=0}^{n-1}\dfrac{1}{a^{2^k}}$, which converges for any $a>1$.
The conclusion is that $T(a^{2^{n+1}})$ is asymptotic to $a^{2^{n+1}}$, unless $r_0+\displaystyle\sum_{k=0}^{\infty}\dfrac{1}{a^{2^k}}=0$.
