Wachstumsverhalten von Funktionen

Definition: $\text{f},\ \text{g}$ seien Funktionen von $\mathbbm{N}$ nach $\mathbbm{R}$

• $\text{g}(n)$ ist $\mathcal{O}(\text{f}(n))$ [auch: $\text{g}$ ist $\mathcal{O}(\text{f})$, $\text{g}(n)=\mathcal{O}(\text{f}(n))$, $\text{g}(n) \in \mathcal{O}(\text{f}(n))$] gdw. $(\exists C \in \mathbbm{R}, \exists n_0 \in \mathbbm{N})[(\forall n \geq n_0) [\vert\text{g}(n)\vert \leq C \cdot \vert\text{f}(n)\vert]]$
  Beispiel: n³ ist nicht $\mathcal{O}\left(\frac{n^3}{\log n}\right)$
• $\text{g}(n)$ ist $\Omega(\text{f}(n))$ gdw. $(\exists C \gt 0, \exists n_0 \in \mathbbm{N})[(\forall n \geq n_0) [\vert\text{g}(n)\vert \geq C \cdot \vert\text{f}(n)\vert]]$
• $\text{g}(n)$ ist $\Theta(\text{f}(n))$ gdw. $\text{g}$ ist $\mathcal{O}(\text{f})$ und $\text{g}$ ist $\Omega(\text{f})$
• $\text{g}(n)$ ist $o(\text{f}(n))$ gdw. $(\forall C \gt 0 \ \exists n_0)[(\forall n \geq n_0)[\vert\text{g}(n)\vert \leq C \cdot \vert\text{f}(n)\vert]]$
• $\text{g}(n)$ ist $\omega(\text{f}(n))$ gdw. $(\forall C \gt 0 \ \exists n_0)[(\forall n \geq n_0)[\vert\text{g}(n) \geq C \cdot \vert\text{f}(n)\vert]]$
• $\text{g}(n)$ ist $\Omega_\infty(\text{f}(n))$ gdw. $(\exists C \gt 0)[\vert\text{g}(n)\vert \geq C \cdot \vert\text{f}(n)\vert \text{ f\uml {u}r unendlich viele } n]$
  Beispiel: $n^2 \sin \frac{\pi}{2} n = \Omega_\infty(n)$
• $\text{g}(n)$ ist $\omega_\infty(\text{f}(n))$ gdw. $(\forall C \gt 0)[\vert\text{g}(n)\vert \geq C \cdot \vert\text{f}(n)\vert] \text{ f\uml {u}r unendlich viele } n]$