in Algorithms
12,823 views
3 votes
3 votes
the solution of recurrence relation

T(n)=2T(floor(sqrt(n))+log n
in Algorithms
12.8k views

2 Comments

T(n)=2T(floor(sqrt(n))+log(sqrt(n))

 

what if question is like this?
0
0
Does this floor have any affect on the back substitution method while finding the time complexity or we can just ignore it while using back substitution method?
0
0

Subscribe to GO Classes for GATE CSE 2022

1 Answer

14 votes
14 votes
 
Best answer

T(n)=2T(⎷n)+logn

Let n=2k

T(2k)=2T(2k/2)+k

Let T(2k)=S(k)

So S(k)=2S(k/2)+k

Using Master Theorem

S(k)=O(k log k)

So T(n)=O(logn log logn)

selected by

5 Comments

https://cs.stackexchange.com/questions/82193/tn-2t-sqrtn-log-n-recurrence

 

We define S(m) to be T(2m), for every possible value of m. Changing the name of the variable, S(M)=T(2M) for every value of M. Substituting M:=m/2, we get S(m/2)=T(2m/2)

 

As an example, suppose that T

is the identity function: T(n)=n. We define S(m)=T(2m)=2m. Then S(m/2)=2m/2.

0
0
S(k)=O(k log k)
So T(n)=O(logn log logn)

This is what is happening at the last step.Sorry if it is silly but tell me if we are replacing k with log n then won't it happen on the LHS as well and thus instead of T(n) the calculation will be of T(log n)= O (logn log logn)?
0
0
How did you write s(m/2) it didn't get it
0
0
Can you please help me with the recurrence relation

T(n) = 2T(root(n)) + n

Some people have concluded it to theta(n) but I am getting same as solution to above problem. Please help me out.
0
0