1

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.

Parcly Taxel
  • 103,344
ash
  • 11
  • 1
    Is $n$ real or integer? Usually $n$ denotes integers. – N. S. Oct 29 '16 at 15:58
  • 1
    In this forum, you are supposed to write your attempts at a solution. Your thoughts. In particular, if it is from a textbook, we may like to know what came just before this. Let us be clear what you ask. We are supposed to solve it, not just find asymptotics? In particular, you (or your source) assert that there is a closed-form solution? – GEdgar Oct 29 '16 at 16:07

1 Answers1

4

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.

Virtuoz
  • 3,656
  • I am unable to solve the sequence in the bracket. Could you please give me some hint to solve it. – ash Nov 08 '16 at 14:15