1.Einleitung
2. Theoretische Grundlagen
3. Suchen
4. Sortieren
5. Dynamische Datenstrukturen
6. Graphen
7. Optimierung
Für eine Funktion f : N → N {\displaystyle f:\mathbb {N} \to \mathbb {N} } ist die Menge Ω ( f ( n ) ) {\displaystyle \Omega (f(n))} wie folgt definiert:
Ω ( f ( n ) ) = { g : N → N | ∃ c ∈ R > 0 , ∃ n o ∈ N ∀ n ≥ n 0 : g ( n ) ≥ c ⋅ f ( n ) } {\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 Ω ( f ( n ) ) {\displaystyle \Omega (f(n))} die Menge aller durch f nach unten beschränkter Funktionen ist und somit die asymptotische untere Schranke ist.
