Informatik

Was ist die $\Omega$-Notation?

Die $\Omega$-Notation beschreibt die untere Grenze des asymptotischen Verhaltens einer Funktion $f(n)$ im Vergleich zu einer Funktion $g(n)$ und wird verwendet, um die minimalen Laufzeiten oder Komplexitäten von Algorithmen anzugeben.

Definition

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

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

Erklärung

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

Beispiel

Wenn $f(n) = 5n^2 + 3n$, dann ist $f(n) \in \Omega(n^2)$, da $5n^2$ für große $n$ die dominierende Terme von $f(n)$ ist.