Analyzing Zeitkomplexität (Poly log vs Polynom)

Question

Angenommen, ein Algorithmus läuft auf

[5n^3 + 8n^2 (lg (n))^4]

Welche der Term erster Ordnung ist? Wäre es der mit dem Polylog oder dem Polynom?

Answer 1

Für jede zwei Konstanten a>0,b>0, log(n)^a ist in o(n^b) (Beachten Sie kleine Notation hier).

Eine Möglichkeit, diese Behauptung zu beweisen, ist zu untersuchen, was passiert, wenn wir auf beiden Seiten eine monoton wachsende Funktion anwenden: die Log-Funktion.

log(log(n)^a)) = a* log(log(n)) 
log(n^b) = b * log(n) 

Da wir wissen, dass wir Konstanten ignorieren können, wenn es um asymptotische Notationen kommt, können wir sehen, dass die Antwort auf „die größer ist“ log(n)^a oder n^b, ist das gleiche wie „die größer“: log(log(n)) und log(b) . Diese Antwort ist viel intuitiver zu beantworten.