When can the Master Theorem actually be applied?

Question

I am quite frustrated over this.

In CLRS 3rd edition, page 95 (chapter 4.5), it mentions that recurrences like

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

cannot be solved with the Master Theorem because the difference

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

is not polynomial.

But then I come across pages like this this where, at the bottom of the page, it mentions the exact same recurrence and says that it CAN be solved with the Master Theorem because it falls into an "extended case 2" even though the difference is non-polynomial. It becomes n lg^2 n (incrementing the log factor on f(n) by one).

Then I come across pages like this where in example (e) seems like a clear application of Extended Case 2 (the recurrence is 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 wrong or is the paper wrong?

Can anyone please clear up the contradictions and make it very clear exactly when Master Theorem can be used and when it cannot? When does the polynomial-difference check matter, and when does it not? Is the extended case 2 usable, or does it actually violate something?

EDIT:

I tried solving recurrence (e) directly from the second paper and I get:

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

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

Answer 1

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

even though it appears to have the proper form: ... You might mistakenly think that case 3 should apply

---

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

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

We define:

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

Using Master theorem case 2:

c = log_2(2) = 1
k = 1

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

So, all conditions to master theorem case 2 apply, and we can deduce:

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

---

Long story short, Master theorem have 3 cases. Each case have it's prerequisites to be applied. Case 3 have more complicated prerequisites, because it also requires convergence.
Since the prerequisites for case 3 does not apply for this formula, you cannot use case 3. However, the prerequisites of case 2 - do apply, and you can use it.