Definition:O Notation/Big-O Notation/General Definition

From ProofWiki
Jump to navigation Jump to search

Definition

Estimate at infinity

Let $\left({X, \tau}\right)$ be a topological space.

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

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


The statement:

$f \left({x}\right) = \mathcal O \left({g \left({x}\right)}\right)$ as $x \to \infty$

is equivalent to:

There exists a neighborhood of infinity $U \subset X$ such that:
$\exists c \in \R: c \ge 0: \forall x \in U: \left\Vert{f \left({x}\right)}\right\Vert \le c \cdot \left\Vert{g \left({x}\right)}\right\Vert$


That is:

$\Vert f \left({x}\right) \Vert \le c \cdot \Vert g \left({x}\right) \Vert$

for all $x$ in a neighborhood of infinity.


Point Estimate

Let $(X,\tau)$ be a topological space.

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

Let $x_0\in X$.

Let $f,g:X\setminus\{x_0\}\to V$ be functions.


The statement

$f(x) = \mathcal O \left({g(x)}\right)$ as $x\to x_0$

is equivalent to:

$\displaystyle \exists c\in \R: c\ge 0 : \exists U\in\tau: x_0\in U : \forall x\in U\setminus\{x_0\} : \Vert f(x)\Vert \leq c\cdot\Vert g(x)\Vert$


That is:

$\Vert f(x)\Vert\leq c\cdot\Vert g(x)\Vert$

for all $x$ in a punctured neighborhood of $x_0$.


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$