Baustein:Landau-Symbole

Aus VoWi
(Weitergeleitet von Baustein:Landau-Notation)
Wechseln zu: Navigation, Suche

Landau-Symbole[Bearbeiten, WP, 4.62 Definition]

Seien (a_{n})_{n\geq 0} und (b_{n})_{n\geq 0} Folgen. Dann schreibt man für n \to \infty:

  1. (i) a_{n}=O(b_{n}), falls es eine Konstante C>0 gibt, so dass \left | \frac{a_{n}}{b_{n}} \right |\leq C für fast alle n\in \mathbb{N} gilt.
  2. (ii) a_{n}=o(b_{n}), falls \lim_{n\rightarrow \infty }\frac{a_{n}}{b_{n}} = 0 gilt.
  3. (iii) a_{n}\sim b_{n}, falls \lim_{n\rightarrow \infty }\frac{a_{n}}{b_{n}} = 1 gilt.