Landau-Symbole: Warum ist n^2 + n Element von O(n^2)

Neue Frage »

Gefahrensucher Auf diesen Beitrag antworten »
Landau-Symbole: Warum ist n^2 + n Element von O(n^2)
Meine Frage:
Hallo

Ich bin gerade über die Definition der Landau-Symbole gestolpert. Wobei ich eigentlich sofort beim ersten hängen geblieben bin. Dort wird folgendes definiert:



Da ich noch aus meinen Algorithmen-Vorlesungszeiten weiss, hat mein Prof z.B. bei n^2 + n gesagt, es ist in O(n^2) enthalten. Irgendwie kam mir das jetzt spanisch vor und wollte es mal anhand der Definition nachprüfen. Und das habe ich versucht wie folgt zu tun:

Meine Ideen:
Wenn f(n) = n^2 + n ist und f(n) Element von O(n^2) sein sollte, müsste die Definition oben ja korrekt sein.
Das würde bedeuten, das es eine Konstante C gibt die für ein n>=n0 die Gleichung |f(n)| <= C |g(n)| erfüllt.
Jetzt war ich versucht diese Konstante zu ermitteln, wobei ich natürlich auf die Gleichung n^2 + n = C * n^2 gestossen bin. Wenn ich das umforme, komme ich auf C >= 1 + 1/n
Das heisst, es gibt keine Konstante, da diese von n abhängen würde => Widerspruch.

Somit kann n^2 + n nicht Element von O(n^2) sein.

Nun ist meine verwunderte Frage, wo habe ich meinen Denkfehler?

Lieben Gruß
Euer Gefahrensucher ;-)
kiste Auf diesen Beitrag antworten »

Wähle C=2, so ist dies für jedes n erfüllt.
Gefahrensucher Auf diesen Beitrag antworten »

Hammer Da steht man direkt davor und sieht es nicht...

Dank Dir smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »