1 votes 1 votes closed with the note: Query resolved. What is the time complexity of the following recurrence relation and step to derive the same $T(n) = T(\sqrt{n}) + log(logn)$ Algorithms time-complexity algorithms recurrence-relation + – VikramRB asked Jan 20, 2019 • closed Jan 21, 2019 by VikramRB VikramRB 1.0k views comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes Take $n=2^m$ then $T(2^m)=T(2^{m/2})+\log m$ $\implies S(m)=S(m/2)+\log m$ Solve using master's theorem .$S(m)=O(\log ^2 m)=T(2^m)$ Put $m=logn \implies T(n)=(\log \log n)^2$ Verma Ashish answered Jan 20, 2019 Verma Ashish comment Share Follow See all 4 Comments See all 4 4 Comments reply VikramRB commented Jan 21, 2019 reply Follow Share How did you derive the 3rd step, m = $2^{m}$ is understod but how $2^{m/2}$ written as m/2 0 votes 0 votes Verma Ashish commented Jan 21, 2019 reply Follow Share We are not replacing $2^m \;by\; m$ but we are changing function T to S. $T(2^m)\implies$ function of m. (S(m)) $T(2^{m/2})\implies$ function of m/2. (S(m/2)) 1 votes 1 votes Hira Thakur commented Oct 11, 2019 reply Follow Share can you please tell me $log^2(logn)$ and $(loglogn)^2$both are same?? 0 votes 0 votes Verma Ashish commented Oct 11, 2019 reply Follow Share Yes..same 0 votes 0 votes Please log in or register to add a comment.