Aufwandsabschätzung: Induktionsbeweis und O-Notation

[mirage228]

Hallo,

In meiner Vorlesung an der Uni nehmen wir für die Aufwandsabschätzung die O-Notation und damit Induktionsbeweis zur Hilfe.

Nun haben wir in einer Übung eine Aufgabe einen Induktionsbeweis für eine O-Notations-Formel zu führen, bei der ich nicht so recht weiterkommen.

Man soll zeigen, dass die Funktion
f(n) = 1/1000 * n^4 + 1000 * n^2 * log(n) Element aus ("E")
O(n^4) ist

Induktionsvorraussetzung ist also:
1/1000 * n^4 + 1000 * n^2 * log(n) < n^4

Beim Induktionsbeweis wähle ich nun eine Konstante c0 vor n^4, welche in diesem Fall auf "1" setze, sowieso ein beliebiges n0, der dann den Induktionsbeginn darstellt (n0 = 1)

Daraus erhält man schonmal (für n = 1):
1/1000 <= 1

Für den Induktionsbeweis macht man nun das ganze für (n + 1):

1/1000 * (n + 1)^4 + 1000 * (n + 1)^2 * log(n + 1) <= (n + 1)^4

Nun an dieser Stelle komme ich nicht weiter. Es gilt ja z.B. oben c0 möglichst geschickt zu wählen um hier u.A. auch mittels der Induktionsvorraussetzung beweisen zu können, dass diese Ungleichung zutrifft.

Wir hatten in der Vorlesung ein Beispiel in der auf der rechten Seite (also bei (n + 1)^4) die Induktionssvorraussetzung verwendet worden ist, damit kam ich allerdings nicht weiter.

Weiß wer von euch Rat oder kann mir evtl. bei dem Ansatz helfen?

Im Anhang noch mal die Aufgabenstellung mit den Originalsymbolen als GIF-Screenshoft aus dem PDF.

Viele Grüße