Otra recurrencia... $T(n)=\sqrt{2n} \cdot T(\sqrt{2n}) + \sqrt{n}$

Question

Estoy tratando de resolver la siguiente recurrencia : $$T(n)=\sqrt{2n}\cdot T(\sqrt{2n}) + \sqrt{n}$$

He probado sustituyendo $n$ para algunas otras variables para transformar el anterior para algo más fácil, sin suerte. A continuación, he utilizado un árbol de recursión en $n$ y conseguí que la suma en cada nivel de $m$ es: $$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).$$ no sé cómo calcular el árbol de profundidad; así que ni siquiera sé si estoy haciendo bien o si debo buscar otro camino. Se agradece la ayuda. Gracias.

Answer 1

Sugiero el siguiente procedimiento. Set $$ m=log_2(n)-1 $$ so that $$ n=2^{m+1} $$ and $$ \sqrt{2n}=2^{\frac{m}{2}+1} $$ A continuación, la definición de $S(m)=\frac{T(2^{m+1})}{2^{m+1}}$ produce$$ \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*} $$que tiene la forma de la que el maestro teorema.