If $ T(n) = \sqrt{2n}T(\sqrt{2n} )+ {n ^ 2} $ , what is complexity of T(n)?
Well, I let $ n = {2 ^ k} $ , $ y(k) = \frac{T({2 ^ k} )}{4 ^ k} $ and I tried to resolve this recurrence by iterations methods, but I saw that it not works here. How I can find the complexity for this recurrence?
Try substituting $n$ by $2^{k+1}$ and consider $S(k)=\frac{T(2^{k+1})}{2^{k+1}}$ which is $T(n)/n$ and this in turn is equal to $2\frac{T(\sqrt{2n})}{\sqrt{2n}} + n$. By observing that $\sqrt{2n}=2^{\frac{k}{2}+1}$ you reduce your recurrence to a simpler one $S(k) = 2S(\frac{k}{2})+2^{k+1}$. This you might find easier to solve.
