21,247 views
2 votes
2 votes

Can masters theorem solve the recurrence 4T(n/2) + n2.logn ? 

it is said that it falls between the case 2 & 3 and no solution possible with this method .can anyone explain it clearly ?
 

3 Answers

Best answer
7 votes
7 votes

$n^{\log_b a} = n^{\log_2 4} = n^2$

i.e. $f(n) = \Omega \left(n^{\log_b a}\right)$. 

Now, to apply Master theorem case 3, we need a positive constant $\epsilon$ such that $f(n) = \Omega \left(n^{\log_b a + \epsilon} \right)$. But here we can't get any such constant and hence we can't apply Master theorem. So, solving by expansion:
$$\begin{align}
T(n) &= 4T \left (\frac{n}{2} \right ) + n^2 \log n\\[1em]
&= 16T\left (\frac{n}{2^2} \right ) + n^2 \log n + n^2 \log \left(\frac{n}{2} \right)\\[1em]
&\quad \vdots\\[1em]
&= 4^{\lg n} + n^2 \left [\log n + \log \left(\frac{n}{2}\right) + \cdots +  \log \left(\frac{n}{\large 2^{\lg n} \normalsize}\right) \right ]\\[1em]
&= 4^{\lg n} + n^2 \cdot \log \Biggl (  n \times \frac{n}{2} \times \cdots \times \large \frac{n}{2^{\lg n}} \normalsize \Biggr )\\[1.5em]
&= n^2 + n^2 \cdot \large \log \left ( \frac{n^{\lg n + 1}}{2^{\lg n \cdot (\lg n +1)/2}} \right )\\[1.5em]
&= n^2 + n^2 \cdot \large \log \left ( \frac{n^{\lg n + 1}}{n^{(\lg n +1)/2}} \right )\\[1.5em]
&= n^2 + n^2 \cdot \large \log \left ( n^{(\lg n + 1)/2}  \right )\\[1.5em]
&= n^2 + n^2 \cdot \frac{\lg n +1}{2} \cdot \log n\\[1em]
\hline
T(n) &= \Theta\left( n^2 \log^2 n\right)
\end{align}$$


Actually we can even use Extended Master theorem which directly gives the asymptotic bound as $\Theta \left(n^2 \log^2 n \right)$.

selected by
2 votes
2 votes

a=4,b=2,k=2,p=1

if a=bthen 

if p>-1 then t(n)=Θ(nlogba.logp+1n)

so,here 4=22

and p>-1

so,T(n)=Θ(n2.log2n)

0 votes
0 votes

Using Extended Masters theorem:

its of form aT(n/b) + n^k *(lonn)^p

a=4,b=2,k=2 ,p=1

a=b^k

case ii> now check p , p=1 >-1

so case iii>->a) T(n)=Theta((n^(log a ))   *   (log n)^(p+1) )  

T(n)=Theta( n^2* (logn)^2)

Related questions

1 votes
1 votes
1 answer
2
0 votes
0 votes
0 answers
4
pradeepchaudhary asked Aug 20, 2018
890 views
T (n) = T (n/2) + 2nUsing Master's Method What is the Complexity Of This Recurrence Relation?Or Using AnyOther Method?