Omega-Notation - Best-Case-Laufzeit#
Während die O-Notation den Worst-Case und die Theta-Notation den Average-Case zeigt, wird mithilfe der Omega-Notation die Best-Case-Laufzeit abegschätzt.
Definition#
Für eine Funktion \(g(n)\) bezeichnet man mit \(Ω(g(n))\) eine Menge von Funktionen mit folgender Eigenschaft:
\(Ω(g(n)) = \{f(n)\) : es ex. positive Konstanten \(c\) und \(n_0\),
so dass \(0 ≤ c ⋅ g(n) ≤ f(n)\) für alle \(n ≤ n_0\}\).
Damit entspricht die Ω-Notation einer qualitativen unteren Schranke.
\(f(n) ∈ Ω ((n))\), wenn
\(f(n) ≥ c ⋅ g(n)\) für \(n ≥ n_0\).