Landau-Symbole

by Bartlomiej Marzec


Posted on 30 Mar 2014



Definition LS1 (Landau-Symbole)
Seien $(a_n), (b_n)$ zwei reelle Zahlenfolgen.
  1. $a_n=\mathcal{O}(b_n)$, falls es ein $C\in\mathbb{R}, C>0$ und $N\in\mathbb{N}$ gibt, mit $|a_n|\leq C*|b_n|\quad\forall n\geq N$
  2. $a_n=\Omega(b_n)$, falls es ein $C\in\mathbb{R}, C>0$ und $N\in\mathbb{N}$ gibt, mit $|a_n|\geq C*|b_n|\quad\forall n\geq N$
  3. $a_n=o(b_n)$, falls es zu jedem $\varepsilon>0$ ein $N\in\mathbb{N}$ gibt mit $|a_n|\leq\varepsilon|b_n|\quad\forall n\geq N$
  4. $a_n\in\Theta(b_n)$, falls $a_n=\mathcal{O}(b_n)$ und $a_n=\Omega(b_n)$
Definition LS2 (Landau-Symbole(2))
Falls $b_n\not=0$ $\forall n\in\mathbb{N}$ gilt:
  • $a_n=\mathcal{O}(b_n) \Leftrightarrow |\frac{a_n}{b_n}|\leq C$ für ein $C>0$
    Interpretation: $a_n$ wächst nicht schneller als $b_n$
  • $a_n=\Omega(b_n)\Leftrightarrow |\frac{a_n}{b_n}\geq C$ für ein $C>0$
    Interpretation: $a_n$ wächst nicht langsamer als $b_n$
  • $a_n=\Theta(b_n)\Leftrightarrow C_1\leq|\frac{a_n}{b_n}\leq C_2$ für $C_1,C_2>0$
    Interpretation: $a_n$ und $b_n$ wachsen gleich schnell
  • $a_n=o(b_n)\Leftrightarrow |\frac{a_n}{b_n}\rightarrow 0$
    Interpretation: $b_n$ wächst viel schneller als $a_n$
Satz LS3
  1. Alle vier Begriffe sind transitiv, d.h. $$a_n=\mathcal{O}(b_n) \text{ und } b_n=\mathcal{O}(c_n) \Rightarrow a_n=\mathcal{O}(c_n)$$ $$a_n=\Omega(b_n) \text{ und } b_n=\Omega(c_n) \Rightarrow a_n=\Omega(c_n)$$ $$a_n=o(b_n) \text{ und } b_n=o(c_n) \Rightarrow a_n=o(c_n)$$ $$a_n=\Theta(b_n) \text{ und } b_n=\Theta(c_n) \Rightarrow a_n=\Theta(c_n)$$
  2. $\Theta$ ist eine Äquivalenzrelation
  3. $a_n=\mathcal{O}(b_n) \Leftrightarrow b_n=\Theta(a_n)$
  4. $a_n=o(b_n) \Rightarrow a_n=\mathcal{O}(b_n)$
  5. $a_n=\mathcal{O}(b_n) \Leftrightarrow a_n=\mathcal{O}(\alpha\cdot b_n)\qquad\forall \text{ konst } \alpha\in\mathbb{R}, |\alpha|>0$

Blog Search

Side Widget Well

Bootstrap's default wells work great for side widgets! What is a widget anyways...?