O Notation quadratisch linear?
Wieso ist n² nicht in O(n), obwohl doch z.b. für c=100 (also 100*n) >1² ist.
6 Antworten
![](https://images.gutefrage.net/media/user/Willibergi/1624532782057_nmmslarge__0_0_120_120_040779a85bcf89fd282fa9af46f30da0.png?v=1624532782000)
Was ist denn dann deine Schranke? (Spoiler: Die kann es nicht geben). Schau dir nochmal die Definition der O-Notation an:
Um zu zeigen, dass eine Funktion g in O(f) liegt, musst du ein positives c und ein natürliches n0 finden, sodass die obige Ungleichung erfüllt ist. Wählst du nun c = 100, müsstest du noch ein n0 finden, sodass für alle n > n0
gilt. Dass das nicht funktionieren kann, zeigt man schnell durch elementare Abschätzungen. Umgekehrt wird ein Schuh draus.
LG
![](https://images.gutefrage.net/media/user/bert00712/1568022780202_nmmslarge__0_0_300_300_9a4334409e63f908baa4b0bff88a688f.jpg?v=1568022780000)
Wie habt ihr das definiert? n^2 ∈ O(n), wenn gilt:
Dies ist offensichtlich falsch.
![](https://images.gutefrage.net/media/user/mihisu/1507493208281_nmmslarge__27_27_495_495_365edc29f3a8f4bb31cf67220050d253.png?v=1507493210000)
Wie habt ihr denn die O-Notation definiert. Wenn ich beispielsweise bei der recht üblichen Definition bleibe, wie sie auf Wikipedia zu finden ist...
https://de.wikipedia.org/wiki/Landau-Symbole#Definition
Dann müsste für n² in O(n) gelten...
Das ist aber falsch. Stattdessen ist...
============
Ansonsten mit...
Dann behauptest du, dass C = 100 ein passendes C wäre, wenn ich dich richtig verstanden habe.
Jedoch muss ja das gleiche C für fast alle n passen. Und für n ≥ 100 passt dieses C nicht mehr. Denn für C = 100 und n ≥ 100 ist eben nicht n² < 100 n, sondern n² ≥ 100 n.
![- (Mathematik, Informatik)](https://images.gutefrage.net/media/fragen-antworten/bilder/337164227/0_big.png?v=1581251148000)
![- (Mathematik, Informatik)](https://images.gutefrage.net/media/fragen-antworten/bilder/337164227/1_big.png?v=1581251148000)
![- (Mathematik, Informatik)](https://images.gutefrage.net/media/fragen-antworten/bilder/337164227/2_big.png?v=1581251148000)
![- (Mathematik, Informatik)](https://images.gutefrage.net/media/fragen-antworten/bilder/337164227/3_big.png?v=1581251148000)
![](https://images.gutefrage.net/media/user/Isomorphismus/1578333977764_nmmslarge__0_0_1200_1200_3174f525c5be5f4e8b22b48adcebaf20.png?v=1578333978000)
Eine Funktion f ist in O(g), wenn es ein N und ein a>0 gibt, sodass für alle n>N gilt:
f(n) < ag(n)
Das stimmt zwar, dass 100n > n² für n = 1 ist, aber für größere n ist das nicht mehr der Fall, nimm zb 1000, dann hat man: 100 * 1000 = 100000 < 1.000.000 = 1000 * 1000
(Diese Definition ist äquivalent zu der von @bert00712)
![](https://images.gutefrage.net/media/user/Isomorphismus/1578333977764_nmmslarge__0_0_1200_1200_3174f525c5be5f4e8b22b48adcebaf20.png?v=1578333978000)
![](https://images.gutefrage.net/media/default/user/12_nmmslarge.png?v=1551279448000)
![](https://images.gutefrage.net/media/user/J0T4T4/1444750593_nmmslarge.jpg?v=1444750593000)
![](https://images.gutefrage.net/media/user/Isomorphismus/1578333977764_nmmslarge__0_0_1200_1200_3174f525c5be5f4e8b22b48adcebaf20.png?v=1578333978000)
![](https://images.gutefrage.net/media/user/Isomorphismus/1578333977764_nmmslarge__0_0_1200_1200_3174f525c5be5f4e8b22b48adcebaf20.png?v=1578333978000)
Ne das ist nicht richtig. Also 4^n ist immer kleiner als 6^n, somit ist 4^n in O(6^n), aber mit welcher Konstante willst du 3^n multiplizieren um auf 6^n zu kommen? Wenn man das Grenzwert-Kriterium von bert00712 anwendet dann bekommt man 4^n / 3^n, das ist ungefähr 1.333... ^n und dieser Wert geht für n gegen unendlich auch gegen unendlich
![](https://images.gutefrage.net/media/default/user/10_nmmslarge.png?v=1551279448000)
Nein. Dafür müsstest du ja eine Kostante finden, so dass c * 3^n > 4^n ist.
Und das ist ja nicht so, 4^n/3^n ist (4/3)^n und das wird mit wachsendem n beliebig groß.
Auch 3^n und 6^n unterscheiden sich nicht durch eine Konstante.
![](https://images.gutefrage.net/media/default/user/14_nmmslarge.png?v=1551279448000)
Es muss ein n0 < n existieren, sodass für alle n gilt n^2 <= c*n
Da reicht es nicht einen Wert einzusetzen
Also ist z.B. 4**n in O(3**n), da z.B. 4**n immer kleiner als 6**n ist?