Wie kann man beweisen, dass $ n ( log_3 (n))^5 = o (n^{1.2}) $?

Question

Dies ist eine Hausaufgabenfrage aus Udi Manbers Buch. Jeder Hinweis wäre schön :)

Ich muss das zeigen:

$ n ( log_3 (n))^5 = o (n^{1.2}) $

Ich habe versucht, Theorem 3.1 des Buches zu verwenden:

$ f (n)^c = o (a^{f (n)}) $ (für $ c> 0 $, $ a> 1 $)

Ersatz:

$ ( log_3 (n))^5 = o (3^{ log_3 (n)}) = o (n) $

aber $ n ( log_3 (n))^5 = o (n cdot n) = o (n^2) ne o (n^{1,2}) $

Vielen Dank für jede Hilfe.

Answer 1

Tun Sie, was Sie getan haben, aber sei $ a = (3^{0,2}) $ ... das sollte es tun, oder?

Der Grund, warum Sie nicht gearbeitet haben, ist wie folgt. Die Big-oh-gebundene ist nicht eng; Während der Logarithmus bis zum fünften in der Tat großer linearer Funktionen ist, ist er auch groß der fünfte Wurzelfunktion. Sie benötigen dieses stärkere Ergebnis (das Sie auch aus dem Satz erhalten können), um das zu tun, was Sie tun.

Answer 2

Eine andere Möglichkeit, intuitiver darüber nachzudenken, ist zu sehen log_3 (n) $ ist $ o (n^{0,04}) $. Protokolle werden immer langsamer als jede konstante Kraft von N, egal wie klein.

Wenn Sie den letzten Satz formalisieren möchten, können Sie Theorem 3 mit einem ausreichend kleinen $ alpha $ verwenden, wie @Rang in dem Kommentar zu der Antwort von @patrick87 erwähnt.