Informatik

Was ist die O-Notation?

Die O-Notation beschreibt das asymptotische Verhalten einer Funktion $f(n)$ im Vergleich zu einer anderen Funktion $g(n)$ und wird verwendet, um die Laufzeit oder Komplexität von Algorithmen zu klassifizieren.

Definition

Eine Funktion $f(n)$ ist in $O(g(n))$, wenn es positive Konstanten $c$ und $n_0$ gibt, sodass für alle $n > n_0$ gilt:

$$f(n) \leq c \cdot g(n)$$

Erklärung

Das bedeutet, dass $f(n)$ maximal so schnell wächst wie $g(n)$, ab einem bestimmten Punkt.

Beispiel

Wenn $f(n) = 3n^2 + 2n + 1$, dann ist $f(n) \in O(n^2)$, da die Funktion für große $n$ durch $c \cdot n^2$ beschränkt werden kann.