Cormen Edition 3 Exercise 4.3 Question 9 (Page No. 88)

Question

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.

Answer 1

$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})$