search
Log In
0 votes
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.
in Algorithms
retagged by
50 views

1 Answer

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

Related questions

0 votes
0 answers
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.
asked Apr 5, 2019 in Algorithms akash.dinkar12 22 views
0 votes
0 answers
2
43 views
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})$.
asked Apr 5, 2019 in Algorithms akash.dinkar12 43 views
0 votes
0 answers
3
35 views
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$.
asked Apr 5, 2019 in Algorithms akash.dinkar12 35 views
0 votes
0 answers
4
41 views
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.
asked Apr 5, 2019 in Algorithms akash.dinkar12 41 views
...