edited by
1,501 views
1 votes
1 votes
edited by

1 Answer

Best answer
2 votes
2 votes

$T(n) = 2 T \left ( \sqrt n \right ) + n$

 

Substitution for $n$:

Let $n = 2^r$. Thus, $r = \log_2 n$. Putting this value of $n$ we get

$T \left ( 2^r \right ) = 2 T \left ( 2^{r/2} \right ) + 2^r$

 

Substitution for $T(\cdot)$:

Let $S(r) = T \left ( 2^r \right )$.

Thus,

$S(r) = 2 S \left (\frac{r}{2} \right ) + 2^r$

 

Use Master Method for $S(r)$

$S(r) = \mathcal O(2^r)$


Substitute back to get solution for $T(\cdot)$

$\begin{align}
T \left ( 2^r \right ) &= S(r) = \mathcal O(2^r) \\
T(r) &= S(\log_2 r) = \mathcal O(2^{\log_2 r}) \\
T(r) &= \mathcal O(r)
\end{align}$

selected by

Related questions

0 votes
0 votes
1 answer
2
lucasbbs asked Feb 28, 2022
6,573 views
How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...
0 votes
0 votes
1 answer
4