O-Notation (Landau-Symbole)

Seien $f, g : N \to N$ . Die Landau-Symbole beschreiben das asymptotische Wachstum:

$O (g)$ (Obere Schranke): $f \in O (g) \Leftrightarrow \exists c, n_{0} : \forall n \geq n_{0} : f (n) \leq c \cdot g (n)$ .
$Ω (g)$ (Untere Schranke): $f \in Ω (g) \Leftrightarrow g \in O (f)$ .
$Θ (g)$ (Exaktes Wachstum): $f \in Θ (g) \Leftrightarrow f \in O (g) \land f \in Ω (g)$ .
$o (g)$ (Strikt kleiner): $f \in o (g) \Leftrightarrow \forall ϵ > 0 \exists n_{0} \forall n \geq n_{0} : f (n) < ϵ \cdot g (n)$ .
$ω (g)$ (Strikt größer): $f \in ω (g) \Leftrightarrow g \in o (f)$ .