Time Complexity for $T(n)=T(\sqrt{n})+\sqrt{n}$

Question

Can you help me figure out the time complexity of $T(n)=T(\sqrt{n})+\sqrt{n}$

Answer 1

Try the Ansatz $T(n)\propto n^p$ so $n^p\sim n^{p/2}+n^{1/2}$. While $p=\tfrac12$ works, if $p<\tfrac12$ then $n^p\in o(n^{p/2}+n^{1/2})=o(n^{1/2})$, whereas if $p>\tfrac12$ then $n^{p/2}+n^{1/2}\sim n^{\max(1/2,\,p/2)}\in o(n^p)$.