Aufgabe zur Groß O Notation?
Hallo, ich habe folgende Aufgabe, aber ich weiß nicht wie ich dort anfangen soll.
Ich weiß das es stimmt, weil immer nur der höchsten Exponent von Interesse ist.
Würde mich über Lösungsansätze freuen.
4 Antworten
Du musst Prüfen, ob es ein C>0 und ein N >0 gibt, sodass f(n)<=C*n^3 für alle n>=N gilt
(Mit f bezeichne ich hier die Funktion im Bild)
Da für alle n>=1 folgendes gilt:
n^2 <= n^3
n <= n^3
1 <= n^3
Bekommst du die Abschätzung:
4n^3+2n^2+10n+5 <= 4n^3 + 2n^3 + 10n^3 + 5n^3 = 21n^3
Somit bekommst du die Ungleichung mit C=21 und N=1
(Captain Obvious speaking).
da aber 16n^3 <=cn^3 für c=16 folgt, daß wir in O(n^3) liegen.
Du darfst natürlich auch die formale Definition nehmen und einfach einsetzen.
Ouha, ich habe die Konstante 5 vergessen, seis drum, die Grundidee ändert sich nicht, siehe Antwort von Jangler13.
Du könntest zeigen, dass ab einem bestimmten n z. B. f(n) < 5 n^3 ist.
(Übrigens gehört streng genommen n -> +unendlich mit dazu)
Weis nach, dass das linke geteilt durch das innerhalb des O-Symbols gegen 4, also insbesondere gegen eine Zahl < unendlich konvergiert und somit durch ein C beschränkt ist. Also ist die linke Seite durch irgendein C*n^3 beschränkt