Definition:Big-O Notation/Real

From ProofWiki
Jump to navigation Jump to search

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

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Big-O_Notation/Real&oldid=611505"