4 votes 4 votes the solution of recurrence relation T(n)=2T(floor(sqrt(n))+log n Algorithms algorithms recurrence-relation + – Sanjay Sharma asked May 26, 2016 retagged Jun 23, 2022 by Lakshman Bhaiya Sanjay Sharma 18.6k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply akankshadewangan24 commented Jul 4, 2017 reply Follow Share T(n)=2T(floor(sqrt(n))+log(sqrt(n)) what if question is like this? 0 votes 0 votes aradhya.jain95 commented Jul 16, 2017 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.
Best answer 15 votes 15 votes 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) ManojK answered May 26, 2016 selected May 26, 2016 by rude ManojK comment Share Follow See all 7 Comments See all 7 7 Comments reply rude commented May 26, 2016 reply Follow Share Bingo :D 1 votes 1 votes shraddha_gami commented Aug 16, 2018 reply Follow Share We assumed 2k = k. but, why you had written k in place of k( S(k)=2S(k/2)+k ) 0 votes 0 votes GateAspirant999 commented Sep 22, 2018 reply Follow Share In this solution, you have put $T(2^k) = S(k)$. This also shown to have effect $T(2^{k/2}) = S(k/2)$ I am not able to understand how is happening. Let me explain what I feel. First of all let me do $T(2^k) = T(m)$, that is use another variable $m$ for lesser confusion and more clarity. Now we have $2^{k/2} = (2^k)^{1/2}$. Putting $2^k = m$ makes it $m^{1/2}$. So, it becomes $T(2^{k/2}) = T(m^{1/2})$-. (But not $T(m/2)$ as in case of given solution which makes it $T(k/2)$). Lets verify this. Let $k = 6$. So $T(2^{k/2}) = T(2^{6/2}) = T(2^3) = T(8). m=2^k=64. T(m^{1/2})=T(64^{1/2}) = T(8)$, which proves it correct. Note that I dont think so using $S()$ instead of original function $T()$ itself makes any difference to the substitution. I have put $T(2^k) = T(m)$, making $T(2^{k/2}) = T(m^{1/2})$ Your solution puts $T(2^k) = S(k)$, making $T(2^{k/2}) = S(m/2)$ Am I missing anything? 1 votes 1 votes Registered user 48 commented Dec 3, 2018 reply Follow Share 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 votes 0 votes Pushpa Singh commented May 24, 2019 reply Follow Share 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 votes 0 votes PRANAVCOOL commented Aug 21, 2019 reply Follow Share How did you write s(m/2) it didn't get it 0 votes 0 votes Anshuman935 commented Dec 5, 2019 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.