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)$.