recurrence

Question

T(n)=sqrt(n).T(sqrt(n))+cn

for n>2 with some positive constant c and T(2)=1

Comments

divide the whole recurrence with $n$

So, it becomes

$\frac{T(n)}{n}= \frac{T(\sqrt{n})}{\sqrt{n}} + c$

We can write it as a new recurrence :-

$S(n) = S(\sqrt{n}) + c$

Put $n= 2^{m}$

$S(2^{m}) = S(2^{m/2}) + c$

Again write it as new recurrence as :-

$f(m) = f(m/2) + c$

It is similar  to binary search.

So, $f(m) = O(lgm)$

So, $S(n) = O(lglgn)$

Since , $S(n)= \frac{T(n)}{n}$

So, $T(n) =O(nlglgn)$

---

can u plz elaborate the first two lines.......

---

We have a recursive equation $T(n) = \sqrt{n}\;*\; T(\sqrt{n}) +cn$

I have divided the whole equation by $n$

So, It becomes $\frac{T(n)}{n} = \sqrt{n}\;*\;\frac{T(\sqrt{n})}{{n}} +\frac{cn}{n}$

(or) $\frac{T(n)}{n} = \frac{T(\sqrt{n})}{{\sqrt{n}}} + c$

Now , Let $\frac{T(n)}{n} = S(n)$

So, $\frac{T(\sqrt{n})}{{\sqrt{n}}}$ will be $S(\sqrt{n})$

So, our recurrence will be :- $S(n) = S(\sqrt{n}) + c$

Tell me if you are not getting anything else. I will explain.

---

getting now
thankyou