Landau-Notation

Beim Vergleichen von Laufzeiten und Speicherplatz ist es oft nicht sinnvoll, diese bis auf lineare Faktoren genau anzugeben. Insbesondere kommt es des Öfteren vor, dass Dinge für kleine Eingaben andere Eigenschaften haben als für größere Eingaben. Deshalb behilft man sich, indem man nur das asymptotische Verhalten betrachtet.

Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal O}(g)$, wenn eine Konstante $0<c\in\mathbb{R}$ existiert, sodass für hinreichend groß gewähltes $x$ stets $|f(x)| < c\cdot |g(x)|$ gilt.

Oft schreibt man, zum Beispiel in der Numerik, $f={\cal O}(g)$ statt $f\in{\cal O}(g)$.

Beispiele:

• Seien $p$ und $q$ Polynome, und $\deg p \le \deg q$. Dann ist $p\in{\cal O}(q)$. Deshalb schreibt man meistens nur die höchste Potenz hin, also zum Beispiel ${\cal O}(x^4)$.
• Funktionen in ${\cal O}(1)$ sind ab hinreichend großer Eingabe durch eine Konstante beschränkt.
• Jedes Polynom $p$ ist in ${\cal O}(e^x)$.

Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal o}(g)$, wenn für alle $\varepsilon>0$ ein $N$ existiert, sodass für alle $n\ge N$ gilt $|f(n)|\le\varepsilon |g(n)|$. Das heißt, $f$ wird beliebig klein gegenüber $g$.