0 votes 0 votes Solve the recurrence $T(n)=3T(\sqrt n) +log\ n$ by making a change of variables.Your solution should be asymptotically tight. Do not worry about whether values are integral. Algorithms cormen algorithms recurrence-relation descriptive + – akash.dinkar12 asked Apr 5, 2019 retagged Apr 5, 2019 by akash.dinkar12 akash.dinkar12 898 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes $T(n)=3T(\sqrt{n})+logn$ Let : $n=2^k$ $T(2^k)=3T(2^{k/2})+log2^k$ Replacing : $T(2^k)=S(k)$ $S(k)=3S(\frac{k}{2})+k$ Using Master theorem : $S(k)=\Theta(k^{1.58})$ $T(2^k)=\Theta(k^{1.58})$ $k=logn$ $T(n)=\Theta((logn)^{1.58})$ KUSHAGRA गुप्ता answered May 8, 2020 KUSHAGRA गुप्ता comment Share Follow See all 0 reply Please log in or register to add a comment.