How to solve below recurrence relation ?

Question

T(n)=2√nT(√n)+n 

In this If we take n=2m then and I divide the entire equation by n so I will get 

T(2^m)/2^m=2T(2^m/2) + 1

Now T(2^m)/2^m=S(m), so equation becomes 

S(m)=2S(m/2)+1 therefore S(m)=⊝(m) so T(2^m)/2^m=⊝(m)  , T(2^m)=2^m⊝(logn)=⊝(nlogn)

Is this correct approach or not ,since I am unable to do it with tree method .

Comments

Reduced form is : 

S(m)=2*2-m/2S(m/2)+1 where  m = 2^n

So proceed with substitution technique....

---

It is the first case of master's theorem , it will be ⊝(m) only .

---

How did you got s(m)=2s(m/2)+1

T(n)=2√nT(√n)+n

Let n=2^m

then T(2^m)=2*2^m/2T(2^m)+2^m

Dividing with 2^m 

T(2^m)/2^m  = 2*2^m/2T(2^m/2)+2^m /2^m

let T(2^m)/2^m  be S(m)

then  S(m)=2*2^-m/2S(m/2)+1

Answer 1

O( n log log n )
Using Back substitution
 

Answer 2

First of all, we use Master's theorem, when the recurrence are of form T(n) = a T(n/b) + f(n)

Tree method is much helpful when the problem is divided into two uneven fractions like

T(n) = T(n/2) + T(n/3) + c

But to solve square root recurrence better you go with substitution.

---

Now, let me tell you, what is problem with you approach,

S(m) =  T(2^m)/2^m

S(m/2) =  T(2^m/2)/2^m/2

this way T(2^m/2)   will become  2^m/2 S(m/2)  not simply S(m/2).

So your recurrence will become

S(m)=2*2^m/2*S(m/2)+1

now to solve this recurrence, you cannot use master's theorem, so go for substitution method only.

For more help refer this link : http://cs.stackexchange.com/questions/6410/solving-a-recurrence-relation-with-%E2%88%9An-as-parameter

 

Comments

I have taken T(2^m)/2^m =S(m) , so obviously T(2^m/2)/2^m/2= S(m/2) ,and hence the recuurence is

S(m)=2S(m/2)+1

---

I think, you should check it again whatever you have written.Its a simple substitution.

You only said, " T(2^m)/2^m =S(m) , so obviously T(2^m/2)/2^m/2= S(m/2) "

This implies T(2^m/2)= 2^m/2*S(m/2) 

So you should substitute this value of T(2^m/2) in the original equation.