O-Kalkül?
Berechne n0 und c aus der formalen Definition des jeweiligen Landau-Symbols.
2 Antworten
f € O(g) heisst:
f(n) <= c * g(n) für grosse n € N, und c konst.
Diese Aussage stimmt nur falls f(x) = log(n^8), nicht (log(n))^8
Man muss also zeigen, dass
log(n^8) <= n^(2/3)
bzw.
8*log(n) <= n^(2/3)
für alle n > n0 gilt.
Rein graphisch ergibt sich das für n0 ~ 50 (mit log10).
Das theoretisch zu beweisen, funktioniert entweder über die Lambert-Funktion oder mit einem Trick (kenne ich leider nicht).
Man benötigt keinen Trick zur Lösung. Sowohl der log wie n^(2/3) sind monoton steigend, d.h. sie können höchstens einen Schnittpunkt haben. Es reicht also ein n0 jenseits des Schnittpunkts anzugeben, dann ist die <= Bedingung für alle n => n0 erfüllt.
Mit (log(n))^8 stimmt die Behauptung nicht. Zum graphischen Beweis einfach die beiden Funktionen (log(x))^8 und x^(2/3) plotten.
Ja und nun? Was bedeutet diese Element-Beziehung denn formal? Schreibe das doch erst mal hin.
c* log^8(n) ≤ n^2/3 bedeutet das
log(n) ∈ O(n) aus der Vorlesung
log(n) ^8 ∈ O(n^8)
Wie mache ich weiter?
Siehe die Antwort von @Rammstein. Schau dir die gegebene Funktion noch mal genau an und überlege den Unterschied zwischen log^8(x) und log(x^8).
c*log(n^8) <= n^(2/3) für alle n => n0. Bitte immer die komplette Definition angeben.
Das kann nicht sein. Schau dir die Funktion
f(x) = (log(x))^8 - x^(2/3)
mal hier
https://rechneronline.de/funktionsgraphen/
an.
in der Aufgabe steht (log(n))^8 :(((