in Algorithms edited by
1,487 views
1 vote
1 vote
in Algorithms edited by
by
1.5k views

4 Comments

$2^{k}T(n\tfrac{1}{2^{k}})+ (n+2n^{1/2}+2^{2}n^{1/2^{2}}+2^{3}n^{1/2^{3}} + 2^{k-1}n^{1/2^{k-1}}$)

Left part                                    Right part

To terminate the series lets assume T(2) is the terminating condition. So the terminating condition will be k=log(log n). Thus the left part will be log n and the right part will be

 

log(n)*1 + GP with first term n common ratio $2n^{1/2}$ Sum till k-1 terms where k=log log(n)

which becomes something like n^{1+ (loglog n)/2 -1/2}
0
0

So, what's the complexity you are getting then?

@Tejasvi96

0
0
I Guess it would be difficult to denote in big O notation but something like $n^{1/2+loglog(n))$.

And it may go exponential too. What is the answer given ?
0
0

1 Answer

2 votes
2 votes
Best answer

$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

4 Comments

S(r)=2S(r2)+2rS(r)=2S(r2)+2r

 

Use Master Method for S(r)S(r)

S(r)=O(2r)

How can you apply Master Method here since $f(r) = 2^r$ is not polynomially larger than $g(r) = r^{log_22} = r$?

0
0

@avistein third case? 

why does it need to be polynomially larger?

0
0
T(N)=O(N) right ?
0
0

Related questions

0 votes
0 votes
1 answer
4