536 views

1 Answer

Best answer
4 votes
4 votes

According to Extended Masters Theorem,

$T(n) = aT(n/b)+n^k\log^p n, a\geq 1, b>1, k \geq 0$ and $p$ can be a real number

  1. if $a> b^k$
    $T(n)=\Theta \left (n^{\log_b a} \right)$
  2. if $a = b^k$
    1. if $p>-1, T(n) = \Theta \left(n^{\log_b a} \log^{p+1} n\right)$
    2. if $p=-1, T(n) = \Theta \left(n^{ \log_b a} \log \log n\right)$
    3. if $p<-1, T(n) = \Theta\left(n^{\log_b a} \right)$
  3. if $a< b^k$
    1.  if $p \geq 0, T(n) = \Theta \left(n^k \log^pn \right)$
    2. if $p<0, T(n) = O \left(n ^k\right)$

in the given question, $a=1,b=2,k=1/2$ and $p=0$

here $a<b^k$ and $p=0$   (case 3(a))

so $T(n) = \Theta\left(n^k \log^pn \right)$

$T(n) = \Theta \left(n ^{1/2}\right)$


Alternatively we can apply Master theorem as given in Cormen, 

$$T(n) = aT(n/b)+ f(n)$$

Here, $a = 1, b = 2, f(n) = n^{1/2}, f(n) = \Omega \left( n^{\log_b a + \epsilon} \right) \implies  n^{1/2} = \Omega\left( n^{\log_2 1 + \epsilon} \right)$, is true for any $\epsilon < \frac{1}{2}$, and thus we have some positive $\epsilon$. So, Case 3 of Master theorem. But Case 3 also requires regularity condition which states, $$af\left(\frac{n}{b} \right)\leq c f(n)$$ for some $c < 1$.

Here, we get 

$af\left(\frac{n}{b} \right) = f\left(\frac{n}{2} \right) = \frac{n^{1/2} }{ \sqrt 2} \leq c f(n)$,

for any $c \leq \frac{1}{\sqrt 2}.$  

So, regularity condition also satisfied and we get $T(n) = \Theta (f(n)) = \Theta \left(n^{1/2}\right)$.

edited by

Related questions

1 votes
1 votes
2 answers
1
1 votes
1 votes
0 answers
2
sumit goyal 1 asked Jan 9, 2018
597 views
$T(n) = 2t(\frac{n}{2}) + \frac{n}{\log n } ; T(1 ) =1$
0 votes
0 votes
1 answer
3
0 votes
0 votes
2 answers
4
sahil_malik asked Sep 11, 2018
303 views
T(n) = 3T( n/3 ) + n/2The answer to the above question says that case 2 of masters theorem is applied here. How is it so?