2. Asymptotik
Wir betrachten Funktionen der Form f : X → ℂ und g : Y → ℂ mit nach oben unbeschränkten Definitionsbereichen X, Y ⊆ ℝ derart, dass ein x0 existiert mit
X ∩ [ x0, ∞ [ = Y ∩ [ x0, ∞ [.
Die Standardbeispiele für diese Definitionsbereiche sind nach oben unbeschränkte reelle Intervalle oder diskrete Mengen wie ℕ oder ℕ* = ℕ − { 0 }. In den meisten Anwendungen ist X = Y oder es gibt kleine Abweichungen wie X = [ 0, ∞ [ und Y = ] 0, ∞ [.
Funktionen dieser Form wollen wir nun in ihrem Wachstum für x → ∞ vergleichen. Dies ist in verschiedenen Weisen möglich, wir können zum Beispiel fordern, dass die Differenz f − g der Funktionen gegen Null konvergiert oder schwächer wenigstens beschränkt ist. Oder dass Quotient f/g gegen 1 strebt. Wir beginnen mit den für die Zahlentheorie besonders wichtigen Quotienten. Die Paradebeispiele sind die Stirling-Formel über das Wachstum der Fakultät und der Primzahlsatz. Danach diskutieren wir allgemeinen Bachmann-Landau-Notationen o, O und Θ, mit deren Hilfe sich Wachstumsvergleiche elegant und suggestiv formulieren lassen.
Notationen, Sprechweisen und Konventionen
(1) | limx f (x) steht im Folgenden immer kurz für limx → ∞ f (x). Analoges gilt für limsup und liminf. |
(2) | Wir sagen, dass eine Eigenschaft ℰ(x) schließlich gilt, wenn es ein x0 ∈ ℝ gibt, sodass ℰ(x) für alle x > x0 erfüllt ist. Die obige Voraussetzung an die Definitionsbereiche von f und g besagt zum Beispiel, dass X und Y schließlich übereinstimmen. |
(3) | Bei Divisionen f/g nehmen wir stillschweigend stets an, dass der Divisor g schließlich ungleich 0 ist. |