Kurs:Algorithmen und Datenstrukturen/Vorlesung/Omega-Notation

$\mathrm{\Omega }$ -Notation

Für eine Funktion $f:\mathbb{N}\to \mathbb{N}$ ist die Menge $\mathrm{\Omega }(f(n))$ wie folgt definiert:

$\mathrm{\Omega }(f(n))=\{g:\mathbb{N}\to \mathbb{N}|\mathrm{\exists }c\in {ℝ}^{>0},\mathrm{\exists }{n}_o\in \mathbb{N}\mathrm{\forall }n\ge n_0:g(n)\ge c\cdot f(n)\}$

Anschaulich formuliert bedeutet das, dass $\mathrm{\Omega }(f(n))$ die Menge aller durch f nach unten beschränkter Funktionen ist und somit die asymptotische untere Schranke ist.