Solve the recurrence relation $T(n)=\sqrt nT(\sqrt n)+\ln n$

Question

Recurrence relation is $T(n)=\sqrt nT(\sqrt n)+\ln n$ if $n>2$ otherwise $T(n)=1$.

No rule can be applied here. Can anyone arrive with a solution.

Answer 1

You can divide both sides by $n$ and obtain $$ \frac{T(n)}{n} = \frac{T(\sqrt{n})}{\sqrt{n}} + \frac{\ln n}{n}. $$ Denote $\phi(n) = T(n)/n$: $$ \phi(n) = \phi (\sqrt{n}) + \frac{\ln n}{n} = \phi(\sqrt[4]{n}) + \frac{\ln \sqrt{n}}{\sqrt{n}} + \frac{\ln n}{n} = \ldots $$ $$ = \ln n \Big(\frac{1}{n} + \frac{1}{2\sqrt{n}} + \frac{1}{4\sqrt[4]{n}} + \ldots \Big). $$ You can easily figure out how many summands are there in the bracket. If you know $\phi(n)$ then you can also find $T(n)$.

Is such form satisfactory for you, or are you looking for the closed form? If so, are you sure that it exists? In such kind of problems asymptotic is usually more important. Probably you are looking for asymptotic? Also initial conditions and domain should be clarified.