Anwenden Fall 3 des Master-Theorems

Question

Introduction to Algorithms CLRS 4.3 (b) hat das Problem

T (n) = 3 * T (n/3) + n/lg (n)

Beachten Sie, dass n^(log a/log b) = n^(3 log/log 3) = 1

die Buch heißt es, dass hier der Master-Theorem Fall 3 nicht da n/log angewendet werden (n) ist nicht polynomiell größer dh es ist asymptotisch kleiner als n^(k) wobei k eine positive Konstante ist.

Meine Frage ist: Nehmen wir k = 0,1 dann ist n/log (n) immer asymptotisch größer als n^(0.1), aber das widerspricht der obigen Aussage. Was mache ich falsch?

Answer 1

IIUC, haben Sie einen Fehler in den Vorläufer des Falles Anwendung 3.

Ihre Wiederholung ist

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

, die in der conventions of the Master Theorem bedeutet, dass a = b = 3

Für the third case Sie n/log (n) haben muss = Ω (n ^c), wobei c> log (3) = 1. Dies trifft in der Tat nicht zu.