6.6 Landau Notation

Wir führen nun zwei geläufige Notationen ein, die das asymptotische Verhalten einer Funktion mit dem asymptotischen Verhalten einer anderen Funktion vergleichen – also ein relatives asymptotisches Verhalten beschreiben.

Sei $D\subseteq ℝ$ eine Teilmenge und $x_0\in \overline{ℝ}$ ein Häufungspunkt (also mit ${\dot{U}}_{\delta }\left(x_0\right)\cap D\ne \varnothing$ für alle $\delta >0$). Seien $f,g:D\to ℝ$ Funktionen. Wir schreiben

falls ein $\delta >0$ und eine Konstante $M>0$ existieren, so dass $\left|f\right(x\left)\right|\le M\left|g\right(x\left)\right|$ für alle $x\in D\cap {\dot{U}}_{\delta }\left(x_0\right)$. In anderen Worten, $f$ ist „ Gross-O“ von $g$ für $x\to x_0$, falls in einer punktierten Umgebung von $x_0$ die Funktion $f$ durch eine Konstante mal $\left|g\right|$ beschränkt werden kann. Obwohl dies für obige Defintion nicht notwendig ist, werden wir eigentlich immer vorraussetzen, dass $g\left(x\right)\ne 0$ für alle $x\in D$ oder zumindest für alle $x\in {\dot{U}}_{{\delta }_0}\left(x_0\right)$ für ein ${\delta }_0>0$. In diesem Fall ist $f$ genau dann Gross-O von $g$, wenn $\frac{f}{g}$ in einer $\delta$-Umgebung von $x_0$ beschränkt ist. Nochmals in anderen Worten ist $f=O\left(g\right)$ gleichbedeutend damit, dass $f$ nicht viel grösser als $g$ ist wenn $x$ in der Nähe von $x_0$ liegt. Zum Beispiel gilt

Der Vorteil der Notation ist, dass wir den Namen (oben $M$) für die obere Schranke nicht einführen. Falls uns diese Konstante nicht besonders interessiert, dann können wir uns dadurch bei Rechnungen von einer Zeile zur nächsten auf das Wesentlich konzentrieren. Man spricht in diesem Zusammenhang auch von der impliziten Konstante, falls diese nach einigen Rechenschritten doch erwähnt werden muss.

Wenn $f$ nicht nur durch $g$ beschränkt ist, sondern asymptotisch gegenüber $g$ vernachlässigbar ist, dann sagen wir, dass $f$ „Klein-o“ von $g$ ist für $x\to x_0$. Genauer formuliert: Wir schreiben

falls für jedes $𝜀>0$ ein $\delta >0$ existiert mit $\left|f\right(x\left)\right|\le 𝜀\left|g\right(x\left)\right|$ für alle $x\in D\cap {\dot{U}}_{\delta }\left(x_0\right)$. Wie zuvor wollen wir meist $g\left(x\right)\ne 0$ auf $D$ annehmen. In diesem Fall gilt $f\left(x\right)=o\left(g\right(x\left)\right)$ für $x\to x_0$ genau dann, wenn

Man beachte, dass, falls die eigentlichen Grenzwerte $\underset{x\to x_0}{\lim }f\left(x\right)$ und $\underset{x\to x_0}{\lim }g\left(x\right)$ existieren und nicht Null sind, sicherlich $f\left(x\right)=O\left(g\right(x\left)\right)$ für $x\to x_0$ erfüllt ist, aber die stärkere Aussage $f\left(x\right)=o\left(g\right(x\left)\right)$ für $x\to x_0$ falsch ist. Beide Notationen sind also vor allem dann interessant, wenn die Grenzwerte entweder null oder unendlich sind. Zum Beispiel gilt

Diese Notationen machen analog Sinn für andere Bewegungen wie zum Beispiel $x\searrow x_0$, allgemeine Filter, und können insbesondere auch für Folgen verwendet werden.

Die Landau Notation wird in vielen Situationen auch als Platzhalter verwendet, um beispielsweise auszudrücken, dass ein Term in einer Summe schneller anwächst oder abfällt als die anderen. In einem Ausdruck der Form

steht der Term $o\left(g\right(x\left)\right)$ für eine implizite Funktion $h:D\to ℝ$ mit der Eigenschaft

also soll $\tilde{f}\left(x\right)=f\left(x\right)+o\left(g\left(x\right)\right)$ die Asymptotik $\tilde{f}\left(x\right)-f\left(x\right)=h\left(x\right)=o\left(g\left(x\right)\right)$ für $x\to x_0$ erfüllen. Dies gilt analog ebenso für die Gross-O Notation.

Beispielsweise schreibt man (nach Polynomdivision mit Rest)

und erinnert sich auf der rechten Seite somit nur an jene Terme, die den Hauptteil der Bewegung $x\to \infty$ ausmacht. Es mag vielleicht überraschen, dass im obigen Beispiel alle drei Formeln zutreffen oder nützlich sein könnten. Doch folgen diese Behauptungen direkt aus der Polynomdivision und je nach Zusammenhang will man vielleicht die etwas genauere Aussage mit Fehler $o\left(1\right)$ oder die gröbere Aussage mit Hilfe des Fehlers $o\left(x\right)$ verwenden.

Derartige asymptotische Aussagen helfen in komplizierteren Argumenten und Berechnungen den Fokus auf die wesentlichen Teile einer Berechnungen zu lenken. Doch liegen in diesem Verstecken von gewissen Ausdrücken auch Risiken für Fehler, zum Beispiel wenn wir die Fehlerterme unbeschränkt oft addieren wollen oder die Fehlerterme von weiteren Parametern abhängen und diese Abhängigkeit auf Grund der Notation vergessen wird. Wir werden die Landau Notation sporadisch aber doch immer wieder einmal einsetzen um das Wesentliche an einer Aussage zu betonen.