3

I am trying to solve the following recurrence relation :

$$g(n) =\sqrt n\cdot g(\sqrt n) +2n + \frac{n-\sqrt n}2$$

The Master theorem does not fulfill because of $\sqrt n$, so I tried to change the variables $m=\log(n)$ and then got stuck when I placed: $S(m):=g(2^m)$

Any suggestions?

Thank you!

Mythomorphic
  • 6,008
user8244016
  • 131
  • 1
    Hint: divide by $n,$, then $, \frac{g(n)}{n}=\frac{g(\sqrt{n})}{\sqrt{n}} + \frac{5}{2} - \frac{1}{2 \sqrt{n}} ,$. – dxiv Jun 10 '17 at 16:39
  • 1
    Consider $$f(k)=2^{-2^k}g(2^{2^k})$$ and show that $$f(k)=f(k-1)+\frac52-\frac1{2^{1+2^{k-1}}}$$ hence $$f(k)=f(0)+\frac52k-\ldots=\Theta(\ldots)$$ which indicates that $$g(n)=\Theta(\ldots)$$ – Did Jun 10 '17 at 17:22
  • @Did and divx thank you both for answering ,I tried to merge your suggestions and I got 2.5log(log(n)) -0.5( sqrt(n)^0.5 + sqrt(n)^0.25 + sqrt(n)^0.125 + ..+0.25 can you help me solve this ? I searched about sum of power series but I still do not know how to solve this. – user8244016 Jun 11 '17 at 08:15
  • @Did thank you I solved it : O(nloglogn) – user8244016 Jun 11 '17 at 09:00

0 Answers0