1 flag 2,623 views
4 votes
4 votes

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(2m)/2m=2T(2m/2) + 1

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

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

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

  • 🚩 Duplicate | 👮 Hira Thakur | 💬 “https://gateoverflow.in/268663/t-n-sqrt-n-t-sqrt-n-n”
1 flag

2 Answers

6 votes
6 votes

O( n log log n )
Using Back substitution
 

1 votes
1 votes

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(2m)/2m

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

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

So your recurrence will become

S(m)=2*2m/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

 

Related questions

0 votes
0 votes
0 answers
1
1 votes
1 votes
0 answers
3
1 votes
1 votes
1 answer
4
iarnav asked Jul 29, 2017
2,442 views
Given RR as -T(n) = 2T(n/2)+n ; n>1T(1) = 1Solve this using only BACK SUBSTITUTION method? Note - I am stuck at T(n)= 2^k.T(n/2^k)+(2^k-1).nand I'm putting 2^k=n Please h...