Landau-Symbole

Beispiel für die Notation von Big O: ${\color {red}f(x)}\in O{\color {blue}(g(x))}$ da es gibt $M>0$ (z.B., $M=1$) und $x_{0}$ (z.B.,$x_{0}=5$), so dass ${\color {red}f(x)}\leq {\color {blue}Mg(x)}$ wenn $x\geq x_{0}$. ⓘ

Die Big-O-Notation ist eine mathematische Notation, die das begrenzende Verhalten einer Funktion beschreibt, wenn das Argument gegen einen bestimmten Wert oder gegen unendlich tendiert. Big O gehört zu einer Familie von Notationen, die von Paul Bachmann, Edmund Landau und anderen erfunden wurden und als Bachmann-Landau-Notation oder asymptotische Notation bezeichnet werden. Der Buchstabe O wurde von Bachmann gewählt, um für Ordnung zu stehen, d. h. für die Ordnung der Annäherung. ⓘ

In der Informatik wird die Big-O-Notation verwendet, um Algorithmen danach zu klassifizieren, wie ihre Laufzeit oder ihr Platzbedarf mit zunehmender Eingabegröße wächst. In der analytischen Zahlentheorie wird die Big-O-Notation häufig verwendet, um eine Grenze für den Unterschied zwischen einer arithmetischen Funktion und einer besser verstandenen Näherung anzugeben; ein berühmtes Beispiel für einen solchen Unterschied ist der Restterm im Primzahlensatz. Die Big-O-Notation wird auch in vielen anderen Bereichen verwendet, um ähnliche Schätzungen vorzunehmen. ⓘ

Die Big-O-Notation charakterisiert Funktionen nach ihren Wachstumsraten: Verschiedene Funktionen mit der gleichen Wachstumsrate können mit der gleichen O-Notation dargestellt werden. Der Buchstabe O wird verwendet, weil die Wachstumsrate einer Funktion auch als die Ordnung der Funktion bezeichnet wird. Die Beschreibung einer Funktion in der Big-O-Schreibweise liefert in der Regel nur eine obere Grenze für die Wachstumsrate der Funktion. ⓘ

In Verbindung mit der Big-O-Notation gibt es mehrere verwandte Notationen, die die Symbole o, Ω, ω und Θ verwenden, um andere Arten von Schranken für asymptotische Wachstumsraten zu beschreiben. ⓘ

Notation	Anschauliche Bedeutung ⓘ
$f=o(g)$ oder $f\in {\begin{smallmatrix}\!{\mathcal {O}}\!\end{smallmatrix}}(g)$	$f$ wächst langsamer als $g$
$f=O(g)$ oder $f\in {\mathcal {O}}(g)$	$f$ wächst nicht wesentlich schneller als $g$
$f\in \Theta (g)$	$f$ wächst genauso schnell wie $g$
$f=\Omega (g)$	$f$ wächst nicht immer langsamer als $g$ (Zahlentheorie)
$f\in \Omega (g)$	$f$ wächst nicht wesentlich langsamer als $g$ (Komplexitätstheorie)
$f\in \omega (g)$	$f$ wächst schneller als $g$

Formale Definition

Sei f, die zu schätzende Funktion, eine reelle oder komplexwertige Funktion und sei g, die Vergleichsfunktion, eine reellwertige Funktion. Beide Funktionen seien auf einer unbeschränkten Teilmenge der positiven reellen Zahlen definiert und $g(x)$ seien streng positiv für alle ausreichend großen Werte von x. Man schreibt

$$f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to \infty$$

wenn der Absolutwert von $f(x)$ höchstens ein positives konstantes Vielfaches von $g(x)$ für alle hinreichend großen Werte von x. Das heißt $f(x)=O{\bigl (}g(x){\bigr )}$ wenn es eine positive reelle Zahl M und eine reelle Zahl x₀ gibt, so dass

$$|f(x)|\leq Mg(x)\quad {\text{ for all }}x\geq x_{0}.$$

ⓘ

In vielen Kontexten wird die Annahme, dass wir an der Wachstumsrate interessiert sind, wenn die Variable x gegen unendlich geht, nicht angegeben, und man schreibt einfach, dass

$$f(x)=O{\bigl (}g(x){\bigr )}.$$

Die Notation kann auch verwendet werden, um das Verhalten von f in der Nähe einer reellen Zahl a zu beschreiben (oft ist a = 0): Wir sagen

$$f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to a$$

wenn es positive Zahlen gibt $\delta$ und M, so dass für alle x mit $0<|x-a|<\delta$,

$$|f(x)|\leq Mg(x).$$

Da g(x) so gewählt wird, dass es für Werte von x, die hinreichend nahe bei a liegen, ungleich Null ist, können diese beiden Definitionen mit Hilfe des Grenzwerts vereinheitlicht werden:

$$f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to a$$

Wenn

$$\limsup _{x\to a}{\frac {\left|f(x)\right|}{g(x)}}<\infty .$$

ⓘ

In der Informatik ist eine etwas restriktivere Definition üblich: $f$ und $g$ müssen beide Funktionen von den positiven ganzen Zahlen zu den nichtnegativen reellen Zahlen sein; $f(x)=O{\bigl (}g(x){\bigr )}$ wenn es positive ganze Zahlen M und n₀ gibt, so dass $f(n)\leq Mg(n)$ für alle $n\geq n_{0}$. Wo nötig, werden endliche Bereiche (stillschweigend) ausgeschlossen von $f$'s und $g$ausgeschlossen, indem n₀ ausreichend groß gewählt wird. (Zum Beispiel, $\log(n)$ ist undefiniert bei $n=0$.) ⓘ

Beispiel

Im allgemeinen Sprachgebrauch ist die O-Schreibweise asymptotisch, d. h. sie bezieht sich auf sehr große x. In diesem Fall wird der Beitrag der "am schnellsten" wachsenden Terme die anderen irgendwann irrelevant machen. Infolgedessen können die folgenden Vereinfachungsregeln angewandt werden:

• Wenn f(x) eine Summe mehrerer Terme ist, kann derjenige mit der größten Wachstumsrate beibehalten werden, während alle anderen weggelassen werden.
• Wenn f(x) ein Produkt aus mehreren Faktoren ist, können alle Konstanten (Terme im Produkt, die nicht von x abhängen) weggelassen werden.

Nehmen wir zum Beispiel an, f(x) = 6x⁴ - 2x³ + 5, und wollen diese Funktion mit Hilfe der O-Schreibweise vereinfachen, um ihre Wachstumsrate zu beschreiben, wenn x gegen unendlich geht. Diese Funktion ist die Summe von drei Termen: 6x⁴, -2x³ und 5. Von diesen drei Termen ist derjenige mit der höchsten Wachstumsrate derjenige mit dem größten Exponenten in Abhängigkeit von x, nämlich 6x⁴. Nun kann man die zweite Regel anwenden: 6x⁴ ist ein Produkt aus 6 und x⁴, wobei der erste Faktor nicht von x abhängt. Wenn man diesen Faktor weglässt, erhält man die vereinfachte Form x⁴. Wir sagen also, dass f(x) ein "großes O" von x⁴ ist. Mathematisch gesehen kann man f(x) = O(x⁴) schreiben. Man kann diese Berechnung anhand der formalen Definition bestätigen: f(x) = 6x⁴ - 2x³ + 5 und g(x) = x⁴. Wenn man die obige formale Definition anwendet, ist die Aussage, dass f(x) = O(x⁴) ist, äquivalent zu seiner Erweiterung,

$$|f(x)|\leq Mx^{4}$$

für eine geeignete Wahl von x₀ und M und für alle x > x₀. Um dies zu beweisen, sei x₀ = 1 und M = 13. Dann gilt für alle x > x₀:

$${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$$

also

$$|6x^{4}-2x^{3}+5|\leq 13x^{4}.$$

ⓘ

Verwendung

Die Notation Big O hat zwei Hauptanwendungsgebiete:

• In der Mathematik wird sie häufig verwendet, um zu beschreiben, wie gut eine endliche Reihe eine gegebene Funktion annähert, insbesondere im Fall einer abgeschnittenen Taylor-Reihe oder einer asymptotischen Erweiterung.
• In der Informatik ist sie für die Analyse von Algorithmen nützlich. ⓘ

In beiden Anwendungen wird die Funktion g(x), die in der O(-) vorkommt, in der Regel so einfach wie möglich gewählt, wobei konstante Faktoren und Terme niedrigerer Ordnung weggelassen werden. ⓘ

Es gibt zwei formal ähnliche, aber deutlich unterschiedliche Verwendungen dieser Notation:

• unendliche Asymptotik
• infinitesimale Asymptotik. ⓘ

Diese Unterscheidung bezieht sich jedoch nur auf die Anwendung und nicht auf das Prinzip - die formale Definition für das "große O" ist in beiden Fällen dieselbe, nur mit unterschiedlichen Grenzen für das Funktionsargument. ⓘ

Unendliche Asymptotik

Graphen von Funktionen, die häufig bei der Analyse von Algorithmen verwendet werden und die Anzahl der Operationen N im Verhältnis zur Eingabegröße n für jede Funktion zeigen ⓘ

Die Big-O-Notation ist nützlich, wenn Algorithmen auf ihre Effizienz hin analysiert werden. Die Zeit (oder die Anzahl der Schritte), die zur Lösung eines Problems der Größe n benötigt wird, kann beispielsweise als T(n) = 4n² - 2n + 2 ermittelt werden. Je größer n wird, desto mehr dominiert der Term n², so dass alle anderen Terme vernachlässigt werden können - wenn beispielsweise n = 500 ist, ist der Term 4n² 1000 Mal so groß wie der Term 2n. Die Vernachlässigung des letztgenannten Terms hätte für die meisten Zwecke vernachlässigbare Auswirkungen auf den Wert des Ausdrucks. Darüber hinaus werden die Koeffizienten irrelevant, wenn man sie mit Ausdrücken anderer Ordnung vergleicht, z. B. mit einem Ausdruck, der einen Term n³ oder n⁴ enthält. Selbst wenn T(n) = 1.000.000n², wenn U(n) = n³ ist, übersteigt letzterer immer den ersteren, sobald n größer als 1.000.000 wird (T(1.000.000) = 1.000.000³ = U(1.000.000)). Außerdem hängt die Anzahl der Schritte von den Details des Maschinenmodells ab, auf dem der Algorithmus ausgeführt wird, aber verschiedene Maschinentypen unterscheiden sich in der Regel nur um einen konstanten Faktor in der Anzahl der Schritte, die zur Ausführung eines Algorithmus erforderlich sind. Die Big-O-Notation fasst also zusammen, was bleibt: Wir schreiben entweder

$T(n)=O(n^{2})$

oder

$T(n)\in O(n^{2})$

und sagen, dass der Algorithmus eine Zeitkomplexität der Ordnung n² hat. Das Zeichen "=" soll nicht "ist gleich" im normalen mathematischen Sinne ausdrücken, sondern eher ein umgangssprachliches "ist", so dass der zweite Ausdruck manchmal als genauer angesehen wird (siehe die Diskussion über das "Gleichheitszeichen" weiter unten), während der erste Ausdruck von einigen als Missbrauch der Notation angesehen wird. ⓘ

Infinitesimale Asymptotik

Big O kann auch verwendet werden, um den Fehlerterm in einer Annäherung an eine mathematische Funktion zu beschreiben. Die signifikantesten Terme werden explizit geschrieben, und die weniger signifikanten Terme werden in einem einzigen Big-O-Term zusammengefasst. Betrachten wir zum Beispiel die Exponentialreihe und zwei Ausdrücke, die gültig sind, wenn x klein ist:

${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\[4pt]&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\[4pt]&=1+x+O(x^{2})&{\text{as }}x\to 0\end{aligned}}$

Der zweite Ausdruck (der mit O(x³)) bedeutet, dass der Absolutwert des Fehlers ex - (1 + x + x²/2) höchstens einige konstante Male |x³| ist, wenn x nahe genug bei 0 liegt. ⓘ

Eigenschaften

Wenn die Funktion f als endliche Summe anderer Funktionen geschrieben werden kann, dann bestimmt die am schnellsten wachsende Funktion die Ordnung von f(n). Ein Beispiel,

$f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$

Wenn eine Funktion durch ein Polynom in n begrenzt werden kann, kann man, wenn n gegen unendlich tendiert, die Terme niedrigerer Ordnung des Polynoms außer Acht lassen. Die Mengen O(nc) und O(cn) sind sehr unterschiedlich. Wenn c größer als eins ist, wächst die letztere viel schneller. Eine Funktion, die für jedes c schneller wächst als nc, wird als Superpolynom bezeichnet. Eine Funktion, die langsamer wächst als eine Exponentialfunktion der Form cn, wird subexponentiell genannt. Ein Algorithmus kann sowohl superpolynomielle als auch subexponentielle Zeit benötigen; Beispiele hierfür sind die schnellsten bekannten Algorithmen für die ganzzahlige Faktorisierung und die Funktion n^{log n}. ⓘ

Wir können alle Potenzen von n innerhalb der Logarithmen ignorieren. Die Menge O(log n) ist genau dasselbe wie O(log(nc)). Die Logarithmen unterscheiden sich nur um einen konstanten Faktor (da log(nc) = c log n) und die große O-Notation ignoriert dies. Ebenso sind Logarithmen mit unterschiedlichen konstanten Basen äquivalent. Andererseits sind Exponentiale mit unterschiedlichen Basen nicht von der gleichen Ordnung. Zum Beispiel sind 2n und 3n nicht von derselben Ordnung. ⓘ

Das Ändern von Einheiten kann sich auf die Reihenfolge des resultierenden Algorithmus auswirken, muss es aber nicht. Eine Änderung der Einheiten ist gleichbedeutend mit der Multiplikation der entsprechenden Variablen mit einer Konstanten, wo immer sie auftaucht. Wenn ein Algorithmus beispielsweise in der Reihenfolge n² abläuft, bedeutet das Ersetzen von n durch cn, dass der Algorithmus in der Reihenfolge c²n² abläuft, und die große O-Notation ignoriert die Konstante c². Dies kann als c²n² = O(n²) geschrieben werden. Wenn ein Algorithmus jedoch in der Größenordnung von 2n abläuft, ergibt das Ersetzen von n durch cn 2^cn = (2c)n. Dies ist im Allgemeinen nicht äquivalent zu 2n. Das Ändern von Variablen kann sich auch auf die Reihenfolge des resultierenden Algorithmus auswirken. Wenn beispielsweise die Laufzeit eines Algorithmus O(n) ist, wenn sie anhand der Anzahl n der Ziffern einer Eingabezahl x gemessen wird, dann ist seine Laufzeit O(log x), wenn sie in Abhängigkeit von der Eingabezahl x selbst gemessen wird, da n = O(log x). ⓘ

Produkt

$f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$

$f\cdot O(g)=O(fg)$ ⓘ

Summe

Wenn $f_{1}=O(g_{1})$ und $f_{2}=O(g_{2})$ dann $f_{1}+f_{2}=O(\max(g_{1},g_{2}))$. Daraus folgt, dass wenn $f_{1}=O(g)$ und $f_{2}=O(g)$ dann $f_{1}+f_{2}\in O(g)$. Mit anderen Worten, diese zweite Aussage besagt, dass $O(g)$ ein konvexer Kegel ist. ⓘ

Multiplikation mit einer Konstanten

Sei k eine Konstante ungleich Null. Dann ist $O(|k|\cdot g)=O(g)$. Mit anderen Worten: Wenn $f=O(g)$, dann $k\cdot f=O(g).$ ⓘ

Mehrere Variablen

Big O (und little o, Ω, usw.) kann auch mit mehreren Variablen verwendet werden. Um big O für mehrere Variablen formal zu definieren, nehmen wir an $f$ und $g$ sind zwei Funktionen, die auf einer Teilmenge von $\mathbb {R} ^{n}$. Wir sagen

$f(\mathbf {x} ){\text{ is }}O(g(\mathbf {x} ))\quad {\text{ as }}\mathbf {x} \to \infty$

wenn und nur wenn es Konstanten gibt $M$ und $C>0$ derart, dass $|f(\mathbf {x} )|\leq C|g(\mathbf {x} )|$ für alle $\mathbf {x}$ mit $x_{i}\geq M$ für einige $i.$ Äquivalent dazu ist die Bedingung, dass $x_{i}\geq M$ für einige $i$ kann geschrieben werden $\|\mathbf {x} \|_{\infty }\geq M$geschrieben werden, wobei $\|\mathbf {x} \|_{\infty }$ die Tschebyscheff-Norm bezeichnet. Zum Beispiel kann die Aussage

$f(n,m)=n^{2}+m^{3}+O(n+m)\quad {\text{ as }}n,m\to \infty$

besagt, dass es Konstanten C und M gibt, so dass

$|f(n,m)-(n^{2}+m^{3})|\leq C|n+m|$

wenn entweder $m\geq M$ oder $n\geq M$ gilt. Diese Definition erlaubt, dass alle Koordinaten von $\mathbf {x}$ ins Unendliche wachsen. Insbesondere ist die Aussage

$f(n,m)=O(n^{m})\quad {\text{ as }}n,m\to \infty$

(d.h., $\exists C\,\exists M\,\forall n\,\forall m\,\cdots$) ist ganz anders als

$\forall m\colon ~f(n,m)=O(n^{m})\quad {\text{ as }}n\to \infty$

(d.h., $\forall m\,\exists C\,\exists M\,\forall n\,\cdots$). ⓘ

Nach dieser Definition ist die Teilmenge, auf der eine Funktion definiert ist, bei der Verallgemeinerung von Aussagen aus dem univariaten Bereich in den multivariaten Bereich von Bedeutung. Zum Beispiel, wenn $f(n,m)=1$ und $g(n,m)=n$, dann $f(n,m)=O(g(n,m))$ wenn wir einschränken $f$ und $g$ auf $[1,\infty )^{2}$definiert sind, aber nicht, wenn sie auf $[0,\infty )^{2}$. ⓘ

Dies ist nicht die einzige Verallgemeinerung von Big O auf multivariate Funktionen, und in der Praxis gibt es eine gewisse Inkonsistenz bei der Wahl der Definition. ⓘ

Fragen der Notation

Gleichheitszeichen

Die Aussage "f(x) ist O(g(x))", wie oben definiert, wird gewöhnlich als f(x) = O(g(x)) geschrieben. Manche halten dies für einen Missbrauch der Notation, da die Verwendung des Gleichheitszeichens irreführend sein könnte, da es eine Symmetrie suggeriert, die diese Aussage nicht hat. Wie de Bruijn sagt, ist O(x) = O(x²) wahr, aber O(x²) = O(x) ist es nicht. Knuth bezeichnet solche Aussagen als "Einweggleichungen", denn wenn die Seiten umgedreht werden könnten, "könnten wir aus den Identitäten n = O(n²) und n² = O(n²) lächerliche Dinge wie n = n² ableiten". In einem anderen Brief wies Knuth auch darauf hin, dass "das Gleichheitszeichen in Bezug auf solche Notationen nicht symmetrisch ist", da in dieser Notation "Mathematiker das =-Zeichen üblicherweise so verwenden, wie sie das Wort "is" im Englischen verwenden: Aristoteles ist ein Mann, aber ein Mann ist nicht unbedingt Aristoteles". ⓘ

Aus diesen Gründen wäre es präziser, die Mengenschreibweise zu verwenden und f(x) ∈ O(g(x)) zu schreiben (gelesen als: "f(x) ist ein Element von O(g(x))" oder "f(x) ist in der Menge O(g(x))"), wobei man sich O(g(x)) als die Klasse aller Funktionen h(x) vorstellt, für die gilt: |h(x)| ≤ C|g(x)| für eine Konstante C. Die Verwendung des Gleichheitszeichens ist jedoch üblich. ⓘ

Andere arithmetische Operatoren

Die Big-O-Notation kann auch in Verbindung mit anderen arithmetischen Operatoren in komplizierteren Gleichungen verwendet werden. Zum Beispiel bezeichnet h(x) + O(f(x)) die Sammlung von Funktionen mit dem Wachstum von h(x) plus einem Teil, dessen Wachstum auf das von f(x) beschränkt ist. Somit,

$g(x)=h(x)+O(f(x))$

dasselbe ausdrücken wie

$g(x)-h(x)=O(f(x)).$ ⓘ

Beispiel

Angenommen, es wird ein Algorithmus entwickelt, der mit einer Menge von n Elementen arbeitet. Seine Entwickler sind daran interessiert, eine Funktion T(n) zu finden, die ausdrückt, wie lange der Algorithmus (in einem beliebigen Zeitmaß) in Abhängigkeit von der Anzahl der Elemente in der Eingabemenge benötigt. Der Algorithmus arbeitet, indem er zunächst ein Unterprogramm zum Sortieren der Elemente in der Menge aufruft und dann seine eigenen Operationen durchführt. Die Sortierung hat eine bekannte Zeitkomplexität von O(n²), und nachdem das Unterprogramm ausgeführt wurde, muss der Algorithmus weitere 55n³ + 2n + 10 Schritte ausführen, bevor er beendet wird. Die gesamte Zeitkomplexität des Algorithmus lässt sich also als T(n) = 55n³ + O(n²) ausdrücken. Hier werden die Terme 2n + 10 unter das schneller wachsende O(n²) subsumiert. Auch hier wird ein Teil der formalen Bedeutung des Symbols "=" außer Acht gelassen, aber es ermöglicht die Verwendung der Notation Big O als eine Art praktischen Platzhalter. ⓘ

Mehrfache Verwendungen

Bei komplizierteren Verwendungen kann O(-) an verschiedenen Stellen in einer Gleichung erscheinen, sogar mehrmals auf jeder Seite. Zum Beispiel gilt Folgendes für $n\to \infty$:

$${\begin{aligned}(n+1)^{2}&=n^{2}+O(n),\\(n+O(n^{1/2}))\cdot (n+O(\log n))^{2}&=n^{3}+O(n^{5/2}),\\n^{O(1)}&=O(e^{n}).\end{aligned}}$$

Die Bedeutung solcher Aussagen ist wie folgt: Für jede Funktion, die jedes O(-) auf der linken Seite erfüllt, gibt es einige Funktionen, die jedes O(-) auf der rechten Seite erfüllen, so dass das Einsetzen all dieser Funktionen in die Gleichung die beiden Seiten gleich macht. Die dritte Gleichung oben bedeutet zum Beispiel: "Für jede Funktion f(n) = O(1) gibt es eine Funktion g(n) = O(en), so dass n^f(n) = g(n)." In Bezug auf die obige "Mengenschreibweise" bedeutet dies, dass die Klasse der Funktionen, die durch die linke Seite dargestellt wird, eine Teilmenge der Klasse der Funktionen ist, die durch die rechte Seite dargestellt wird. Bei dieser Verwendung ist das "=" ein formales Symbol, das im Gegensatz zur üblichen Verwendung von "=" keine symmetrische Beziehung darstellt. So impliziert z. B. n^O(1) = O(en) nicht die falsche Aussage O(en) = n^O(1). ⓘ

Schriftsatz

Das große O wird als kursives Großbuchstaben-"O" gesetzt, wie im folgenden Beispiel: $O(n^{2})$. In TeX wird es durch die Eingabe von O im mathematischen Modus erzeugt. Im Gegensatz zu den Bachmann-Landau-Notationen mit griechischem Namen benötigt es kein spezielles Symbol. Einige Autoren verwenden jedoch die kalligrafische Variante ${\mathcal {O}}$ stattdessen. ⓘ

Ordnungen der üblichen Funktionen

Hier ist eine Liste von Funktionsklassen, die bei der Analyse der Laufzeit eines Algorithmus häufig vorkommen. In jedem Fall ist c eine positive Konstante und n wächst unbegrenzt. Die langsamer wachsenden Funktionen werden im Allgemeinen zuerst aufgeführt. ⓘ

Schreibweise	Bezeichnung	Beispiel ⓘ
$O(1)$	Konstante	Feststellen, ob eine Binärzahl gerade oder ungerade ist; Berechnen $(-1)^{n}$; Verwendung einer Nachschlagetabelle mit konstanter Größe
$O(\log \log n)$	doppelt logarithmisch	Anzahl der Vergleiche bei der Suche nach einem Element mit Hilfe der Interpolationssuche in einem sortierten Feld mit gleichmäßig verteilten Werten
$O(\log n)$	logarithmisch	Suche nach einem Element in einem sortierten Feld mit binärer Suche oder einem ausgeglichenen Suchbaum sowie alle Operationen in einem binomischen Heap
$O((\log n)^{c})$ ${\textstyle c>1}$	polylogarithmisch	Die Matrix-Kettenordnung kann in polylogarithmischer Zeit auf einer parallelen Maschine mit wahlfreiem Zugriff gelöst werden.
$O(n^{c})$ ${\textstyle 0<c<1}$	Bruchteilspotenz	Suche in einem k-d-Baum
$O(n)$	linear	Suche nach einem Element in einer unsortierten Liste oder in einem unsortierten Array; Addition zweier n-Bit-Ganzzahlen durch Ripple-Carry
$O(n\log ^{*}n)$	n log-Stern n	Triangulation eines einfachen Polygons mit dem Seidel-Algorithmus oder dem Union-Find-Algorithmus. Beachten Sie, dass $\log ^{*}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{cases}}$
$O(n\log n)=O(\log n!)$	linearithmisch, loglinear, quasilinear oder "n log n"	Durchführen einer schnellen Fourier-Transformation; schnellstmögliche Vergleichssortierung; Heapsort und Merge-Sortierung
$O(n^{2})$	quadratisch	Multiplikation zweier n-stelliger Zahlen mit einem einfachen Algorithmus; einfache Sortieralgorithmen wie Bubble Sort, Selection Sort und Insertion Sort; (Worst-Case-)Schranke für einige in der Regel schnellere Sortieralgorithmen wie Quicksort, Shellsort und Tree Sort
$O(n^{c})$	polynomial oder algebraisch	Parsing von baumadjungierten Grammatiken; Maximum Matching für bipartite Graphen; Ermittlung der Determinante mit LU-Zerlegung
$L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ ${\textstyle 0<\alpha <1}$	L-Notation oder subexponentiell	Faktorisierung einer Zahl mit Hilfe des quadratischen Siebs oder des Zahlenfeldsiebs
$O(c^{n})$ ${\textstyle c>1}$	exponentiell	Suche nach der (exakten) Lösung des Problems des Handlungsreisenden mit Hilfe der dynamischen Programmierung; Bestimmung der Äquivalenz zweier logischer Aussagen mit Hilfe der Brute-Force-Suche
$O(n!)$	faktoriell	Lösung des Handelsreisenden-Problems mittels Brute-Force-Suche; Erzeugung aller unbeschränkten Permutationen einer Menge; Bestimmung der Determinante mit Laplace-Erweiterung; Aufzählung aller Partitionen einer Menge

Die Aussage $f(n)=O(n!)$ wird manchmal abgeschwächt zu $f(n)=O\left(n^{n}\right)$ um einfachere Formeln für die asymptotische Komplexität abzuleiten. Für beliebige $k>0$ und $c>0$, $O(n^{c}(\log n)^{k})$ ist eine Teilmenge von $O(n^{c+\varepsilon })$ für jede $\varepsilon >0$und kann daher als Polynom mit einer größeren Ordnung betrachtet werden. ⓘ

Verwandte asymptotische Notationen

Big O wird in der Informatik häufig verwendet. Zusammen mit einigen anderen verwandten Notationen bildet es die Familie der Bachmann-Landau-Notationen. ⓘ

Little-o-Notation

Intuitiv bedeutet die Behauptung "f(x) ist o(g(x))" (lies "f(x) ist little-o von g(x)"), dass g(x) viel schneller wächst als f(x). Wie zuvor sei f eine reelle oder komplexwertige Funktion und g eine reelle Funktion, beide definiert auf einer unbeschränkten Teilmenge der positiven reellen Zahlen, so dass g(x) für alle ausreichend großen Werte von x streng positiv ist. Man schreibt

$f(x)=o(g(x))\quad {\text{ as }}x\to \infty$

wenn es für jede positive Konstante ε eine Konstante gibt $x_{0}$ derart, dass

$|f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x_{0}.$

Zum Beispiel hat man

$2x=o(x^{2})$ und $1/x=o(1),$     sowohl als $x\to \infty .$ ⓘ

Der Unterschied zwischen der Definition der big-O-Notation und der Definition von little-o besteht darin, dass erstere für mindestens eine Konstante M gelten muss, während letztere für jede noch so kleine positive Konstante ε gelten muss. Auf diese Weise macht die little-o-Notation eine stärkere Aussage als die entsprechende big-O-Notation: Jede Funktion, die little-o von g ist, ist auch big-O von g, aber nicht jede Funktion, die big-O von g ist, ist auch little-o von g. Zum Beispiel, $2x^{2}=O(x^{2})$ aber $2x^{2}\neq o(x^{2})$. ⓘ

Da g(x) ungleich Null ist oder zumindest ab einem bestimmten Punkt ungleich Null wird, ist die Beziehung $f(x)=o(g(x))$ äquivalent zu

$\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ (und dies ist in der Tat die ursprüngliche Definition der Little-O-Notation durch Landau). ⓘ

Little-o berücksichtigt eine Reihe von arithmetischen Operationen. Zum Beispiel,

wenn c eine Konstante ungleich Null ist und $f=o(g)$ dann $c\cdot f=o(g)$, und

Wenn $f=o(F)$ und $g=o(G)$ dann $f\cdot g=o(F\cdot G).$

Sie erfüllt auch eine Transitivitätsbeziehung:

Wenn $f=o(g)$ und $g=o(h)$ dann $f=o(h).$ ⓘ

Big-Omega-Notation

Eine andere asymptotische Notation ist $\Omega$gelesen "großes Omega". Es gibt zwei weit verbreitete und unvereinbare Definitionen der Aussage ⓘ

$f(x)=\Omega (g(x))$ als $x\to a$, ⓘ

wobei a eine reelle Zahl ist, ∞ oder -∞, wobei f und g reelle Funktionen sind, die in einer Umgebung von a definiert sind, und wobei g in dieser Umgebung positiv ist. ⓘ

Die Hardy-Littlewood-Definition wird hauptsächlich in der analytischen Zahlentheorie verwendet, die Knuth-Definition hauptsächlich in der Komplexitätstheorie; die Definitionen sind nicht äquivalent. ⓘ

Die Hardy-Littlewood-Definition

Im Jahr 1914 führten Godfrey Harold Hardy und John Edensor Littlewood das Symbol $\Omega$ mit der Bedeutung ⓘ

$f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0$ ⓘ

ein. Also ist $f(x)=\Omega (g(x))$ die Negation von $f(x)=o(g(x))$. ⓘ

Im Jahr 1916 führten dieselben Verfasser zwei neue Symbole $\Omega _{R}$ und $\Omega _{L}$ mit den Bedeutungen ⓘ

$f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$; ⓘ

$f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0$ ⓘ

ein. Also ist $f(x)=\Omega _{R}(g(x))$ die Negation von $f(x)<o(g(x))$ und $f(x)=\Omega _{L}(g(x))$ die Negation von $f(x)>o(g(x))$. ⓘ

Im Gegensatz zu einer späteren Aussage von Donald E. Knuth verwendete Landau diese drei Symbole im Jahre 1924 mit den gleichen Bedeutungen. ⓘ

Diese Hardy-Littlewood-Symbole sind Prototypen, sie werden nie genau so verwendet. $\Omega _{R}$ ist zu $\Omega _{+}$ und $\Omega _{L}$ zu $\Omega _{-}$ geworden. ⓘ

Diese drei Symbole $\Omega ,\Omega _{+},\Omega _{-}$ sowie $f(x)=\Omega _{\pm }(g(x))$ (dies bedeutet, dass die beiden Eigenschaften $f(x)=\Omega _{+}(g(x))$ und $f(x)=\Omega _{-}(g(x))$ erfüllt sind) werden heute noch systematisch in der analytischen Zahlentheorie verwendet. ⓘ

Einfache Beispiele

Wir haben ⓘ

$\sin x=\Omega (1)$ als $x\to \infty ,$ ⓘ

und genauer gesagt ⓘ

$\sin x=\Omega _{\pm }(1)$ als $x\to \infty .$ ⓘ

Wir haben ⓘ

$\sin x+1=\Omega (1)$ als $x\to \infty ,$ ⓘ

und genauer gesagt ⓘ

$\sin x+1=\Omega _{+}(1)$ als $x\to \infty ;$ ⓘ

jedoch ⓘ

$\sin x+1\not =\Omega _{-}(1)$ als $x\to \infty .$ ⓘ

Wir haben ⓘ

und speziell ⓘ

Wir haben ⓘ

und speziell ⓘ

aber ⓘ

$\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ ⓘ

Die Knuth-Definition

1976 veröffentlichte Donald Knuth einen Aufsatz, in dem er die Verwendung des $\Omega$-Symbols zur Beschreibung einer stärkeren Eigenschaft zu rechtfertigen. Knuth schrieb: "Für alle Anwendungen, die ich bisher in der Informatik gesehen habe, ist eine stärkere Anforderung ... viel angemessener". Er definierte ⓘ

$f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ ⓘ

mit dem Kommentar: "Obwohl ich Hardy und Littlewoods Definition von $\Omega$geändert habe, fühle ich mich dazu berechtigt, weil ihre Definition keineswegs weit verbreitet ist und weil es andere Wege gibt, das zu sagen, was sie in den vergleichsweise seltenen Fällen, in denen ihre Definition zutrifft, sagen wollen." ⓘ

Familie der Bachmann-Landau-Notationen

Schreibweise	Bezeichnung	Beschreibung	Formale Definition	Definition der Grenze ⓘ
$f(n)=o(g(n))$	Kleines O; Kleines Oh	f wird asymptotisch von g dominiert	$\forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|<k\cdot g(n)$	$\lim _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}=0$
$f(n)=O(g(n))$	Groß O; Groß Oh; Groß Omicron	$|f|$ ist oben durch g (bis zu einem konstanten Faktor) asymptotisch begrenzt	$\exists k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\cdot g(n)$	$\limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}<\infty$
$f(n)=\Theta (g(n))$	Großes Theta	f ist sowohl nach oben als auch nach unten asymptotisch durch g begrenzt	$\exists k_{1}>0\,\exists k_{2}>0\,\exists n_{0}\,\forall n>n_{0}\colon$ $k_{1}\cdot g(n)\leq |f(n)|\leq k_{2}\cdot g(n)$	$f(n)=O(g(n))$ und $f(n)=\Omega (g(n))$ (Knuth-Version)
$f(n)\sim g(n)$	In der Größenordnung von	f ist asymptotisch gleich g	$\forall \varepsilon >0\,\exists n_{0}\,\forall n>n_{0}\colon \left|{\frac {f(n)}{g(n)}}-1\right|<\varepsilon$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1$
$f(n)=\Omega (g(n))$	Big Omega in der Komplexitätstheorie (Knuth)	f ist unten asymptotisch durch g begrenzt	$\exists k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\geq k\cdot g(n)$	$\liminf _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}>0$
$f(n)=\omega (g(n))$	Kleines Omega	f dominiert g asymptotisch	$\forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|>k\cdot g(n)$	$\lim _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}=\infty$
$f(n)=\Omega (g(n))$	Großes Omega in der Zahlentheorie (Hardy-Littlewood)	$|f|$ wird nicht asymptotisch von g dominiert	$\exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon |f(n)|\geq k\cdot g(n)$	$\limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}>0$

Die Grenzwertdefinitionen nehmen an $g(n)>0$ für hinreichend große $n$. Die Tabelle ist (teilweise) vom kleinsten zum größten sortiert, in dem Sinne, dass $o,O,\Theta ,\sim ,$ (Knuths Version von) $\Omega ,\omega$ auf Funktionen entsprechen $<,\leq ,\approx ,=,$$\geq ,>$ auf der reellen Linie entsprechen (die Hardy-Littlewood-Version von $\Omega$entspricht jedoch keiner solchen Beschreibung). ⓘ

Die Informatik verwendet das große $O$, großes Theta $\Theta$, kleines $o$, kleines Omega $\omega$ und Knuths großes Omega $\Omega$ Notationen. Die analytische Zahlentheorie verwendet häufig die Bezeichnungen big $O$, kleines $o$, Hardy-Littlewoods großes Omega $\Omega$ (mit oder ohne die Indizes +, - oder ±) und $\sim$ Bezeichnungen. Das kleine Omega $\omega$ Notation wird in der Analysis nicht so häufig verwendet. ⓘ

Verwendung in der Informatik

Informell, insbesondere in der Informatik, kann die große O-Notation oft etwas anders verwendet werden, um eine asymptotische enge Schranke zu beschreiben, wo die Verwendung der großen Theta-Θ-Notation in einem bestimmten Kontext sachlich angemessener sein könnte. Betrachtet man zum Beispiel eine Funktion T(n) = 73n³ + 22n² + 58, so sind alle der folgenden Möglichkeiten im Allgemeinen akzeptabel, aber engere Schranken (wie die Nummern 2 und 3 unten) werden in der Regel gegenüber lockeren Schranken (wie Nummer 1 unten) stark bevorzugt.

1. T(n) = O(n¹⁰⁰)
2. T(n) = O(n³)
3. T(n) = Θ(n³)

Die äquivalenten englischen Aussagen lauten entsprechend:

1. T(n) wächst asymptotisch nicht schneller als n¹⁰⁰
2. T(n) wächst asymptotisch nicht schneller als n³
3. T(n) wächst asymptotisch so schnell wie n³.

Während also alle drei Aussagen wahr sind, ist in jeder von ihnen immer mehr Information enthalten. In einigen Bereichen wird jedoch die große O-Notation (Nummer 2 in den obigen Listen) häufiger verwendet als die große Theta-Notation (Nummer 3 in den obigen Listen). Wenn beispielsweise T(n) die Laufzeit eines neu entwickelten Algorithmus für die Eingabegröße n darstellt, könnten die Erfinder und Benutzer des Algorithmus eher geneigt sein, eine obere asymptotische Grenze für die Laufzeit anzugeben, ohne eine explizite Aussage über die untere asymptotische Grenze zu machen. ⓘ

Andere Notation

In ihrem Buch Introduction to Algorithms betrachten Cormen, Leiserson, Rivest und Stein die Menge der Funktionen f, die folgende Bedingungen erfüllen ⓘ

$f(n)=O(g(n))\quad (n\to \infty )~.$ ⓘ

In einer korrekten Schreibweise kann diese Menge z. B. O(g) genannt werden, wobei ⓘ

$O(g)=\{f:{\text{there exist positive constants}}~c~{\text{and}}~n_{0}~{\text{such that}}~0\leq f(n)\leq cg(n){\text{ for all }}n\geq n_{0}\}.$ ⓘ

Die Autoren stellen fest, dass die Verwendung des Gleichheitsoperators (=) zur Bezeichnung der Mengenzugehörigkeit anstelle des Mengenzugehörigkeitsoperators (∈) ein Missbrauch der Notation ist, aber Vorteile hat. Innerhalb einer Gleichung oder Ungleichung steht die Verwendung der asymptotischen Notation für eine anonyme Funktion in der Menge O(g), wodurch Terme niedrigerer Ordnung eliminiert werden, was z. B. dazu beiträgt, unwesentliche Unordnung in Gleichungen zu reduzieren:

$2n^{2}+3n+1=2n^{2}+O(n).$ ⓘ

Erweiterungen der Bachmann-Landau-Notationen

Eine andere Notation, die manchmal in der Informatik verwendet wird, ist Õ (soft-O): f(n) = Õ(g(n)) ist eine Abkürzung für f(n) = O(g(n) logk n) für ein gewisses k. Einige Autoren schreiben O^* für den gleichen Zweck. Im Wesentlichen handelt es sich dabei um eine Big-O-Notation, bei der logarithmische Faktoren ignoriert werden, weil die Wachstumsrateneffekte einer anderen superlogarithmischen Funktion eine Wachstumsratenexplosion für große Eingabeparameter anzeigen, die für die Vorhersage schlechter Laufzeitleistungen wichtiger ist als die feineren Effekte, die von dem/den logarithmischen Wachstumsfaktor(en) verursacht werden. Diese Notation wird häufig verwendet, um die "Erbsenzählerei" bei Wachstumsraten zu vermeiden, die als zu eng begrenzt für die vorliegende Problematik angegeben werden (da logk n immer o(n^ε) für jede Konstante k und jedes ε > 0 ist). ⓘ

Auch die Notation L, definiert als

$L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$

ist geeignet für Funktionen, die zwischen polynomiell und exponentiell liegen, was die $\ln n$. ⓘ

Verallgemeinerungen und verwandte Verwendungen

Die Verallgemeinerung auf Funktionen, die Werte in jedem normierten Vektorraum annehmen, ist einfach (Ersetzen der absoluten Werte durch Normen), wobei f und g ihre Werte nicht im selben Raum annehmen müssen. Eine Verallgemeinerung auf Funktionen g, die Werte in einer beliebigen topologischen Gruppe annehmen, ist ebenfalls möglich. Der "Begrenzungsprozess" x → xo kann auch verallgemeinert werden, indem man eine beliebige Filterbasis einführt, d. h. auf gerichtete Netze f und g. Die o-Notation kann verwendet werden, um Ableitungen und Differenzierbarkeit in ganz allgemeinen Räumen zu definieren, und auch (asymptotische) Äquivalenz von Funktionen,

$f\sim g\iff (f-g)\in o(g)$

was eine Äquivalenzrelation und ein restriktiverer Begriff ist als die Beziehung "f ist Θ(g)" von oben. (Sie reduziert sich auf lim f / g = 1, wenn f und g positive reellwertige Funktionen sind.) Zum Beispiel ist 2x Θ(x), aber 2x - x ist nicht o(x). ⓘ

Geschichte (Bachmann-Landau-, Hardy- und Vinogradov-Notationen)

Das Symbol O wurde erstmals vom Zahlentheoretiker Paul Bachmann 1894 im zweiten Band seines Buches Analytische Zahlentheorie eingeführt. Der Zahlentheoretiker Edmund Landau übernahm es und wurde dadurch inspiriert, 1909 die Notation o einzuführen; daher werden beide nun Landau-Symbole genannt. Diese Notationen wurden in der angewandten Mathematik in den 1950er Jahren für die asymptotische Analyse verwendet. Das Symbol $\Omega$ (im Sinne von "ist nicht ein o von") wurde 1914 von Hardy und Littlewood eingeführt. Hardy und Littlewood führten 1916 auch die Symbole $\Omega _{R}$ ("rechts") und $\Omega _{L}$ ("links") ein, Vorläufer der modernen Symbole $\Omega _{+}$ ("ist nicht kleiner als ein kleines o von") und $\Omega _{-}$ ("ist nicht größer als ein kleines o von"). Daher werden die Omega-Symbole (mit ihren ursprünglichen Bedeutungen) manchmal auch als "Landau-Symbole" bezeichnet. Diese Notation $\Omega$ wurde spätestens seit den 1950er Jahren in der Zahlentheorie verwendet. In den 1970er Jahren wurde das große O in der Informatik von Donald Knuth popularisiert, der die verwandte Theta-Notation einführte und eine andere Definition für die Omega-Notation vorschlug. ⓘ

Landau hat die großen Theta- und kleinen Omega-Symbole nie verwendet. ⓘ

Hardy's Symbole waren (in Bezug auf die moderne O-Notation)

$f\preccurlyeq g\iff f\in O(g)$   und   $f\prec g\iff f\in o(g);$ ⓘ

(Hardy definierte oder verwendete jedoch nie die Notation $\prec \!\!\prec$, noch $\ll$, wie manchmal berichtet wurde). Hardy führte die Symbole $\preccurlyeq$ und $\prec$ (sowie einige andere Symbole) in seinem 1910 erschienenen Traktat "Orders of Infinity" ein und verwendete sie nur in drei Arbeiten (1910-1913). In seinen verbleibenden fast 400 Arbeiten und Büchern verwendete er durchweg die Landau-Symbole O und o. ⓘ

Hardys Notation wird heute nicht mehr verwendet. Andererseits führte der russische Zahlentheoretiker Ivan Matveyevich Vinogradov in den 1930er Jahren seine Notation $\ll$ein, die in der Zahlentheorie zunehmend anstelle der $O$ Notation. Wir haben

$f\ll g\iff f\in O(g),$

und häufig werden beide Notationen in ein und derselben Arbeit verwendet. ⓘ

Das große O steht ursprünglich für "Ordnung" (Bachmann 1894) und ist somit ein lateinischer Buchstabe. Weder Bachmann noch Landau nennen es jemals "Omicron". Das Symbol wurde viel später (1976) von Knuth als großes Omikron angesehen, wahrscheinlich in Anlehnung an seine Definition des Symbols Omega. Die Ziffer Null sollte nicht verwendet werden. ⓘ

Erstmals drückte der deutsche Zahlentheoretiker Paul Bachmann 1894 „durch das Zeichen $O(n)$ eine Größe aus […], deren Ordnung in Bezug auf $n$ die Ordnung von $n$ nicht überschreitet […].“ Der ebenfalls deutsche Zahlentheoretiker Edmund Landau, durch den die $O$- und $o$-Symbolik bekannt wurde und mit dessen Namen sie insbesondere im deutschen Sprachraum heute verbunden ist, übernahm Bachmanns Bezeichnung und führte zudem die $o$-Bezeichnung für „von kleiner Ordnung“ ein. ⓘ

Sonderfall: Omega-Symbol

Zahlentheoretische Notation

Die strenge Notation $f\in \Omega (g)$ wird in der Zahlentheorie nie benutzt und man schreibt weniger streng immer $f=\Omega (g)$. Dies bedeutet hier „$f$ ist ein Omega von $g$“. ⓘ

Folgerung

Für jede Funktion $f$ werden durch

$\Omega (f),{\mathcal {O}}(f),\Theta (f),o(f),\omega (f)$

jeweils Mengen von Funktionen beschrieben. Es gelten folgende Beziehungen zwischen diesen:

${\begin{aligned}\Theta (f)&\subseteq {\mathcal {O}}(f)\\\Theta (f)&\subseteq \Omega (f)\\\Theta (f)&={\mathcal {O}}(f)\cap \Omega (f)\\\omega (f)&\subseteq \Omega (f)\\o(f)&\subseteq {\mathcal {O}}(f)\\\emptyset \,&=\,\omega (f)\cap o(f)\end{aligned}}$ ⓘ

Notationsfallen

Vergessener Grenzwert

Eine weitere Falle besteht darin, dass oft nicht angegeben wird, auf welchen Grenzwert sich das Landausymbol bezieht. Der Grenzwert ist aber wesentlich; so ist beispielsweise

${\tfrac {1}{x}}\in o\left({\tfrac {1}{\sqrt {x}}}\right)$

für $x\!\uparrow \!\infty$, nicht aber für den einseitigen Grenzwert $x\!\downarrow \!0$ mit

${\tfrac {1}{x}}\in {\mathcal {O}}\left({\tfrac {1}{\sqrt {x}}}\right)(x\!\downarrow \!0)~.$

Jedoch wird normalerweise der zu betrachtende Grenzwert aus dem Zusammenhang klar und Mehrdeutigkeiten treten nur selten auf. ⓘ

Anwendung in der Komplexitätstheorie

In der Komplexitätstheorie werden die Landau-Symbole vor allem verwendet, um den (minimalen, mittleren oder maximalen) Zeit- oder Speicherplatzbedarf eines Algorithmus zu beschreiben. Man spricht dann von Zeitkomplexität bzw. Platzkomplexität. Die Komplexität kann vom verwendeten Maschinenmodell abhängen. In der Regel nimmt man jedoch ein „normales“ Modell an, zum Beispiel ein der Turingmaschine äquivalentes. ⓘ