Definition:Landau Symbols

From ProofWiki
Jump to navigation Jump to search

Definition

The Landau symbols are the $\OO$ and $\mathcal o$ that are used in the definition of big-$\OO$ notation and little-$\mathcal o$ notation:


Big-$\OO$ Notation

Let $f$ and $g$ be real-valued or complex-valued functions defined on a neighborhood of $+ \infty$ in $\R$.


The statement:

$\map f x = \map \OO {\map g x}$ as $x \to \infty$

is equivalent to:

$\exists c \in \R_{\ge 0}: \exists x_0 \in \R: \forall x \in \R: \paren {x \ge x_0 \implies \size {\map f x} \le c \cdot \size {\map g x} }$


That is:

$\size {\map f x} \le c \cdot \size {\map g x}$

for $x$ sufficiently large.


This statement is voiced $f$ is big-O of $g$ or simply $f$ is big-O $g$.


Little-$\mathcal o$ Notation

Let $\map g x \ne 0$ for $x$ sufficiently large.


$f$ is little-o of $g$ as $x \to \infty$ if and only if:

$\ds \lim_{x \mathop \to \infty} \ \frac {\map f x} {\map g x} = 0$


Source of Name

This entry was named for Edmund Georg Hermann Landau.


Sources