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

Question

the solution of recurrence relation

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

Comments

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?

Answer 1

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

Let n=2^k

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

Let T(2^k)=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)

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.

---

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

---

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.