Informatik

Was ist die kleine o-Notation?

Die kleine o-Notation beschreibt eine echte asymptotische Obergrenze: $f(n)$ wächst strikt langsamer als $g(n)$.

Definition

Eine Funktion $f(n)$ ist in $o(g(n))$, wenn für jede positive Konstante $c$ ein $n_0$ existiert, so dass für alle $n > n_0$ gilt:

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

Erklärung

Das bedeutet, dass $f(n)$ asymptotisch kleiner ist als $g(n)$, was bedeutet, dass $g(n)$ die dominierende Funktion ist.

Beispiel

Wenn $f(n)=n$ und $g(n)=n^2$, dann ist $f(n)\in o(n^2)$, denn $\lim_{n\to\infty} n/n^2=0$.