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 Show 4 previous comments 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.