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

50 views
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.

retagged

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

## Related questions

1
22 views
Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n)=T(\alpha n) +T((1-\alpha)n) +cn$,where $\alpha$ is a constant in the range $0<\alpha<1$ and $c>0$ is also constant.
Show that case 3 of the master theorem is overstated, in the sense that the regularity condition $af(n/b)\geq cf(n)$ for some constant $c<1$ implies that there exists a constant $\epsilon >0$ such that $f(n)=\Omega(n^{log_ba+\epsilon})$.
Show that if $f(n)=\Theta(n^{log_ba}\lg^kn )$, where $k\geq0$ then the master recurrence has solution $T(n) =\Theta(n^{log_ba} \lg^{k+1}n)$.For simplicity, confine your analysis to exact powers of $b$.
Consider the regularity condition $af(n/b) \leq cf(n)$ for some constant $c<1$,which is part of case 3 of the master theorem. Give an example of constants $a\geq 1$ and $b>1$ and a function $f(n)$ that satisfies all the conditions in case 3 of the master theorem except the regularity condition.