Definition:Big-O Notation/Real
Definition
Estimate at infinity
Let $f$ and $g$ be real 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-$\OO$ of $g$ or simply $f$ is big-$\OO$ $g$.
Point Estimate
Let $x_0 \in \R$.
Let $f$ and $g$ be real-valued or complex-valued functions defined on a punctured neighborhood of $x_0$.
The statement:
- $\map f x = \map \OO {\map g x}$ as $x \to x_0$
is equivalent to:
- $\exists c \in \R_{\ge 0}: \exists \delta \in \R_{>0}: \forall x \in \R : \paren {0 < \size {x - x_0} < \delta \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 all $x$ in a punctured neighborhood of $x_0$.
Also known as
The big-$\OO$ notation, along with little-$\oo$ 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 functions appearing in the $\OO$-estimate be positive or strictly positive.
Examples
Example: $10 \times$ Function at $+\infty$
Let $f: \R \to \R$ be the real function defined as:
- $\forall x \in \R: \map f x = 10 x$
Then:
- $\map f x = \map \OO x$
as $x \to \infty$.
Example: Sine Function at $+\infty$
Let $f: \R \to \R$ be the real function defined as:
- $\forall x \in \R: \map f x = \sin x$
Then:
- $\map f x = \map \OO 1$
as $x \to \infty$.
Example: $x = \map \OO {x^2}$ at $+\infty$
Let $f: \R \to \R$ be the real function defined as:
- $\forall x \in \R: \map f x = x$
Then:
- $\map f x = \map \OO {x^2}$
as $x \to \infty$.
Sources
- 1979: G.H. Hardy and E.M. Wright: An Introduction to the Theory of Numbers (5th ed.) ... (previous) ... (next): $\text I$: The Series of Primes: $1.6$ Some notations
- 1988: Dominic Welsh: Codes and Cryptography ... (previous) ... (next): Notation