${\displaystyle \Omega }$ -Notation

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

${\displaystyle \Omega (f(n))=\{g:\mathbb {N} \to \mathbb {N} |\exists c\in \mathbb {R} ^{>0},\exists n_{o}\in \mathbb {N} \ \forall n\geq n_{0}:g(n)\geq c\cdot f(n)\}}$

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