# Another recurrence… $T(n)=\sqrt{2n} \cdot T(\sqrt{2n}) + \sqrt{n}$

I'm trying to solve the following recurrence : $$T(n)=\sqrt{2n}\cdot T(\sqrt{2n}) + \sqrt{n}$$

I've tried substituting $n$ for some other variables to transform the above to something easier without luck. Then I used a recursion tree on $n$ and I got that the sum at each level $m$ is: $$2\sqrt{2}\cdot \left(\frac{n}{2}\right)^{3/2^{m}},$$ and the term $$T \left(2 \left(\frac{n}{2}\right)^{3/2^{m-1}} \right).$$ I don't know how to calculate the tree's depth; well I don't even know if I doing this correctly or if I should find another way. Help is appreciated. Thanks.

-
If you set $S(n)=\frac{T(n)}{n}$ and divide your recurrence by $n$, you get $S(n)=\sqrt{2}S(\sqrt{2n})+\frac{1}{\sqrt{n}}$. – vadim123 Apr 30 '13 at 3:22
+1 for showing some work on the problem – Ross Millikan Apr 30 '13 at 3:28

I suggest proceeding as follows. Set $$m=log_2(n)-1$$ so that $$n=2^{m+1}$$ and $$\sqrt{2n}=2^{\frac{m}{2}+1}$$ Then defining $S(m)=\frac{T(2^{m+1})}{2^{m+1}}$ produces\begin{align*} S(m) & =\frac{T(n)}{n} = 2\frac{T(\sqrt{2n})}{\sqrt{2n}}+\frac{1}{\sqrt{n}}\\ & = 2S\left(\frac{m}{2}\right)+\frac{1}{2^\frac{m+1}{2}} \end{align*}which has the form of the the master theorem.