When can I apply the master's theorem?

Question

I am very upset about this.

The third issue of CLRS, p. 95 (chapter 4.5), mentions relapses such as

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

cannot be solved using the main theorem, since the difference

f(n)/n^(log_b(a)) = (n lg n)/n^1 = lg n

is not a polynomial.

But then I come across pages, for example this , where the same repetition is mentioned at the bottom of the page and says that this can be solved using the main theorem, because it falls into "extended case 2", although the difference is not polynomial. It becomes n lg^2 n (increasing the log factor by f(n) by one).

Then I come across pages like this , where in example (e) it seems like a clear application of Extended Case 2 (repeating T(n) = 4T(n/2) + n^2 lg n ), but then the solution is not n^2 log^2 n , but rather n^2 log n ! Am I mistaken or is the article incorrectly written?

Can anyone clarify the contradictions and make it very clear when the Master Theorem can be used, and when it is impossible? When is the polynomial difference checked, and when not? Is extended case 2 usable, or is it really breaking something?

EDIT:

I tried to solve recursion (e) directly from the second article, and I get:

T(n) = n^2 lg^2(n)/2 + n^2 lg(n)/2

Is this not a big theta n^2 lg^2 n ?

Answer 1

The book says that it cannot be solved using Case 3 :

even if it has the correct form: ... you might mistakenly think that case 3 should apply

---

However, this recurrence formula can be solved using the main theorem, case 2.

 T(n) = 2T(n/2) + nlgn: 

Define:

 a = 2, b = 2, f(n) = nlgn 

Usage Case with the main theorem 2 :

 c = log_2(2) = 1 k = 1 

And f(n) really is in Theta(nlogn) .

So, all the conditions for considering Theorem 2 are applicable, and we can conclude:

T(n) is in Theta(n^c * log(n)^(k+1)) = Theta(n*log(n)^2)

---

In short, Teacher’s theorem has 3 cases. In each case, there are prerequisites for application. Case 3 has more complex premises, since it also requires convergence.
Since the prerequisites for case 3 do not apply to this formula, you cannot use case 3. However, the prerequisites for case 2 apply, and you can use it.