Aufgabe zur Groß O Notation?

4 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

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

Woher ich das weiß:Studium / Ausbildung – Mache derzeit meinen Mathematik Master

(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)

Woher ich das weiß:Hobby – Hobby, Studium, gebe Nachhilfe

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