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