Introduction To Algorithms

Question

T(N) = 3T(N/4) + NlogN

T(N) = 2T(N/2)+ NlogN

Master theorem applicable to this ??

Answer 1

Second one is not applicable

Comments

Can u explain in detail

---

Find the ratio of f(n) /$n^{loga}$ (baseb) .

If the ratio ia logn then master is not applicable

---

How to decide  function is polynomially larger or asymptotically larger ??

---

For every example will it work ?

Ratio = logn => master not applicable

Otherwise => Applicable

---

Yes alwaya applicable .

---

So What is The Time Complexity of

                               T(n)=2T(n/2)+nlogn

---

@bhavnakumrawat5 : Answer will be, $\Theta (nlog^{^{2}}n)$

Here is the reference https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Inadmissible_equations

---

The basic form of Master's theorem won't be applicable but extended Master's theorem will work.

---

@gauravkc you are right, this question is worthless trying.

---

Sir whether it is basic master's theorem or advanced master's theorem??

Please reply.

---

@Ashish: No body is sir here...and yes it's advanced I think...

---

In advanced master's theorem there is no such restriction is given.

---

I'm talking about this-

---

@abhishekh Mehtasee the pic uploaded by

@verma Ashish according to this ,

a=2,b=2,k=1 so a=$b^k$ is true

So complexity will be $\theta(nlog^2n)$

From where you read about it$(\frac{f(n)}{n^{log_ba}}=log_ba)$then master is not applicable

 

please give the reference about it

---

@abhishek Mehta @shaik

Please suggest whether pic uploaded by Abhishek is correct?