Quando si può applicare effettivamente il Teorema Master?

Question

Sono abbastanza frustrato per questo.

In CLRS 3a edizione, pagina 95 (capitolo 4.5), si informa che le recidive come

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

non può essere risolto con il Maestro Teorema perché la differenza

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

è non polinomiale.

Ma poi mi imbatto in pagine come this dove, nella parte inferiore della pagina, menziona esattamente la stessa ricorrenza e dice che PUO 'essere risolto con il Teorema Master perché cade in un "caso esteso 2" anche anche se la differenza è non polinomiale. Diventa n lg^2 n (incrementando il fattore di registro su f(n) di uno).

Poi io vengo da una pagina all'altra, come this dove nell'esempio (e) sembra una chiara applicazione di Case Esteso 2 (la ricorrenza è T(n) = 4T(n/2) + n^2 lg n), ma allora la soluzione non è n^2 log^2 n, ma piuttosto n^2 log n! Mi sbaglio o la carta è sbagliata?

Qualcuno può chiarire le contraddizioni e chiarire esattamente quando è possibile utilizzare il Teorema master e quando non è possibile? Quando interviene il controllo della differenza polinomiale e quando no? Il caso esteso 2 è utilizzabile o viola effettivamente qualcosa?

EDIT:

Ho provato a risolvere recidiva (e) direttamente dalla seconda carta e ottengo:

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

Non è questo grande theta n^2 lg^2 n?

Answer 1

Il libro afferma che non può essere risolto utilizzando Case 3:

anche se sembra avere la forma corretta: ... Si potrebbe erroneamente pensare che il caso 3 dovrebbe applicarsi

---

Tuttavia, questa formula di ricorrenza può essere risolta utilizzando il teorema master, caso 2.

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

Definiamo:

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

Utilizzando Master theorem case 2:

c = log_2(2) = 1 
k = 1 

E f(n) è infatti in Theta(nlogn).

Quindi, tutte le condizioni per maestro caso teorema 2 si applicano, e si può dedurre:

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

---

Per farla breve, teorema hanno 3 casi. Ogni caso ha i prerequisiti da applicare. Il caso 3 ha prerequisiti più complessi, perché richiede anche la convergenza.
Poiché i prerequisiti per il caso 3 non si applicano a questa formula, non è possibile utilizzare il caso 3. Tuttavia, i prerequisiti del caso 2 - si applicano e possono essere utilizzati.