small o

Einfache Sprache

Def. small o

Gegeben zwei Funktionen $f,g:\mathbb N\to\mathbb R^+$. Wir sagen das $f(n)$ in small o von $g(n)$ ist, also $f(n)=o(g(n))$, wenn

$$\lim_{n\to\infty}\frac{f(n)}{g(n)} = 0\;.$$

Also heißt $f(n)=o(g(n))$ das für alle $c\in\mathbb R^+$ existiert ein $n_0\in\mathbb N$ so, dass für alle $n\geq n_0$ gilt $f(n)

Beispiel Small o

Es gilt:

1. $\sqrt=o(n)$
2. $n = o(n \log \log n)$
3. $n \log \log n = o(n \log n)$
4. $n \log n = o(n^2)$
5. $n^2 = o(n^3)$

Beachte das $f(n)$ niemals in $o(f(n))$.