12,823 views
the solution of recurrence relation

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

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

what if question is like this?
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?

### Subscribe to GO Classes for GATE CSE 2022

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)

by

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.

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)?
How did you write s(m/2) it didn't get it

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.