O-Notation

Die O-Notation (auch Landau-Notation, Landau-Symbole oder auf Englisch big O notation) wird verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben.

Definition

Seien zwei Funktionen gegeben. Man schreibt:

wenn es ein und ein gibt, ab dem gilt:

Einfach gesagt

Wenn eine Funktion zur Klasse gehört, dann wächst maximal so stark wie . Man schreibt dann:

Siehe auch

• Übersicht Komplexitätsklassen

Weitere Symbole

• Groß-Omega-Notation
  • Untere Schranke
  • wächst mindestens wie
• Groß-Theta-Notation
  • Exakte Schranke
  • wächst wie

Beispiel: Asymptotische Notation für

Beispiel: Asymptotische Notation für

Beispiele für