retagged by
898 views

1 Answer

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

Related questions

0 votes
0 votes
0 answers
1
akash.dinkar12 asked Apr 5, 2019
182 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...
0 votes
0 votes
0 answers
2
akash.dinkar12 asked Jun 28, 2019
322 views
Show that in the recurrence$T(n)=\max_{0<q\leq n-1} (T(q)+T(n-q-1))+\Theta(n)$$T(n)=\Omega(n^2)$
0 votes
0 votes
0 answers
4