Definition:Big-O Notation/Real/Infinity

Definition

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

Also defined as

Some authors require that $\map g x$ be nonzero for $x$ sufficiently large.

Sources

• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): order notation