Informatik

Was ist die kleine $\omega$-Notation?

Die kleine $\omega$-Notation beschreibt eine strengere untere Grenze für das asymptotische Verhalten einer Funktion $f(n)$ im Vergleich zu einer Funktion $g(n)$. Sie wird verwendet, um anzugeben, dass $f(n)$ schneller wächst als $g(n)$, wenn $n$ gegen unendlich geht.

Definition

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

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

Erklärung

Das bedeutet, dass $f(n)$ asymptotisch größer ist als $g(n)$, was darauf hinweist, dass $f(n)$ die dominierende Funktion ist.

Beispiel

Wenn $f(n) = n^2$ und $g(n) = n$, dann ist $f(n) \in \omega(n)$, da $n^2$ für große $n$ immer schneller wächst als ein Vielfaches von $n$.