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.
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) $$Das bedeutet, dass $f(n)$ maximal so schnell wächst wie $g(n)$, ab einem bestimmten Punkt.
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.