Definition:O Notation/Big-O Notation

From ProofWiki
Jump to navigation Jump to search


Definition

Big-O notation occurs in a variety of contexts.

Sequences

Let $\sequence {a_n}$ and $\sequence {b_n}$ be sequences of real or complex numbers.


$a_n$ is big-O of $b_n$ if and only if

$\exists c \in \R_{\ge 0}: \exists n_0 \in \N: \forall n \in \N: \paren {n \ge n_0 \implies \size {a_n} \le c \cdot \size {b_n} }$

That is:

$\size {a_n} \le c \cdot \size {b_n}$

for all sufficiently large $n$.

This is denoted:

$a_n = \map \OO {b_n}$


Real Analysis

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$.


Complex Analysis

Let $f$ and $g$ be complex functions defined for all complex numbers whose modulus is sufficiently large.


The statement:

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

is equivalent to:

$\exists c \in \R_{\ge 0}: \exists r_0 \in \R: \forall z \in \C: \paren {\cmod z \ge r_0 \implies \cmod {\map f z} \le c \cdot \cmod {\map g z} }$


That is:

$\cmod {\map f z} \le c \cdot \cmod {\map g z}$

for all $z$ in a neighborhood of infinity in $\C$.


General Definition

Let $\struct {X, \tau}$ be a topological space.

Let $V$ be a normed vector space over $\R$ or $\C$ with norm $\norm {\,\cdot\,}$.

Let $f, g : X \to V$ be functions.


The statement:

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

is equivalent to:

There exists a neighborhood of infinity $U \subset X$ such that:
$\exists c \in {\R}_{\ge 0}: \forall x \in U: \norm {\map f x} \le c \norm {\map g x}$


That is:

$\norm {\map f x} \le c \norm {\map g x}$

for all $x$ in a neighborhood of infinity.


Dependence on Parameters

Let $X$ be a topological space.

Let $V$ be a normed vector space over $\R$ or $\C$ with norm $\norm {\, \cdot \,}$

Let $x_0 \in X \cup \set \infty$.

Let $A$ be a set.

Let $X_\alpha$ be a subset of $X$ for every $\alpha \in A$, which, if $x_0 \ne \infty$, contains $x_0$.

Let $f_\alpha : X_\alpha \setminus \set {x_0} \to V$ be a mapping for every $\alpha \in A$.

Let $g : X \to V$ be a mapping.

The statement:

$f_\alpha = \map {\OO_\alpha} g$ as $x \to x_0$

is equivalent to:

$\forall \alpha \in A : f_\alpha = \map \OO g$ as $x \to x_0$


The $\OO$-estimate is said to be independent of $\alpha \in A$ if and only if:

there exists a neighborhood $U$ of $x_0$ in $X$ such that:
$\exists c \in \R: c \ge 0 : \forall \alpha \in A : \forall x \in \paren {U \setminus \set {x_0} } \cap X_\alpha : \norm {\map {f_\alpha} x} \le c \cdot \norm {\map g x}$

That is, if the implied constant and implied neighborhood can be chosen the same for all $\alpha \in A$.


Uniform Estimates

Let $X$ be a set.

Let $V$ be a normed vector space over $\R$ or $\C$ with norm $\norm {\, \cdot \,}$.

Let $f, g : X \to V$ be mappings.


Then $f$ is big $\OO$ of $g$ uniformly if and only if:

$\exists c > 0 : \forall x \in X : \norm {\map f x} \le c \cdot \norm {\map g x}$

This is denoted:

$f = \map \OO g$


Implied Constant

From the definition of the limit of a function, it can be seen that this is also equivalent to:

$\exists c \in \R: c > 0, k \ge 0: \forall n > k, f \left({n}\right) \le c g \left({n}\right)$

For some fixed $k$ (appropriate to the function under consideration) the infimum of such $c$ is called the implied constant.


Also known as

The big-$\OO$ notation, along with little-$\mathcal o$ notation, are also referred to as Landau's symbols or the Landau symbols, for Edmund Georg Hermann Landau.


In analytic number theory, sometimes Vinogradov's notations $f \ll g$ or $g \gg f$ are used to mean $f = \map \OO g$.

This can often be clearer for estimates leading to typographically complex error terms.


Some sources use an ordinary $O$:

$f = \map O g$


Also defined as

Some authors require that the inequality be valid on the entire domain of definition.

On $\mathsf{Pr} \infty \mathsf{fWiki}$, this is known as a uniform big-$\OO$ estimate.


The statement $f = \map \OO g$ is sometimes seen to be defined as:

$\ds \exists \alpha \in \R: \alpha \ge 0 : \lim_{x \mathop \to \infty} \frac {\map f x} {\map g x} = \alpha$

However, requiring that the limit exists is generally viewed to be too restrictive.


Also see

  • Results about asymptotic notations can be found here.


Sources