Big O
Einfache Sprache
$f(n)=O(g(n))$ besagt das $f$ weniger oder gleich $g$ ist wenn man konstante Faktoren vernachlässigt.
Def. Big O
Gegeben zwei Funktionen $f,g:\mathbb N\to\mathbb R^+$. Wir sagen das $f(n)$ in big O von $g(n)$ ist, also $f(n)=O(g(n))$, wenn $c,n_0\in \mathbb N^+$ existieren so, dass für alle $n\in\mathbb N$ mit $n\geq n_0$ gilt,
$$f(n)\leq cg(n)\;.$$Wenn $f(n)=O(g(n))$, dann sagen wir auch $g(n)$ ist eine (asymptotische) obere Schranke für $f(n)$.
Beispiel Big O
Sei $f_1(n) = 5n^3+2n^2+22n+6$. Dann ist $f_1(n)=O(n^3)$. aber auch $f_1(n)=O(n^4)$. $f_1(n)$ ist aber nicht in big O von $n^2$