Landau-Symbole

Landau-Symbole (auch O-Notation, englisch big O notation) werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben.

In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an.

Die Komplexitätstheorie verwendet sie, um Probleme danach zu klassifizieren, wie „schwierig“ oder aufwändig sie zu lösen sind. Zu „leichten“ Problemen existiert ein Algorithmus, dessen Laufzeit sich durch ein Polynom beschränken lässt; als „schwer“ gelten Probleme, für die man keinen Algorithmus gefunden hat, der weniger schnell als exponentiell wächst. Man nennt sie (nicht) polynomiell lösbar.

Notation	Anschauliche Bedeutung (immer ohne Berücksichtigung von Konstanten)
${\displaystyle f=o(g)}$ oder ${\displaystyle f\in {\begin{smallmatrix}\!{\mathcal {O}}\!\end{smallmatrix}}(g)}$	${\displaystyle f}$ wächst langsamer als ${\displaystyle g}$
${\displaystyle f=O(g)}$ oder ${\displaystyle f\in {\mathcal {O}}(g)}$	${\displaystyle f}$ wächst höchstens genauso schnell wie ${\displaystyle g}$
${\displaystyle f\in \Theta (g)}$	${\displaystyle f}$ wächst genauso schnell wie ${\displaystyle g}$
${\displaystyle f=\Omega (g)}$	${\displaystyle f}$ wächst nicht immer langsamer als ${\displaystyle g}$ (Zahlentheorie)
${\displaystyle f\in \Omega (g)}$	${\displaystyle f}$ wächst mindestens genauso schnell wie ${\displaystyle g}$ (Komplexitätstheorie)
${\displaystyle f\in \omega (g)}$	${\displaystyle f}$ wächst schneller als ${\displaystyle g}$