# Definition:O Notation/Big-O Notation/Real

## Definition

### Estimate at infinity

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 {\mathcal O} {\map g x}$ as $x \to \infty$

is equivalent to:

- $\exists c \in \R: c \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$**.

### 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:

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

is equivalent to:

- $\exists c \in \R: c \ge 0: \exists \delta \in \R : \delta > 0 : \forall x \in \R : \left({0 < \left\lvert{x - x_0}\right\rvert < \delta \implies \left\lvert{f \left({x}\right)}\right\rvert \le c \cdot \left\lvert{g \left({x}\right)}\right\rvert}\right)$

That is:

- $\left\lvert{f \left({x}\right)}\right\rvert \le c \cdot \left\lvert{g \left({x}\right)}\right\rvert$

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$

## Also defined as

Some authors require that the functions appearing in the $\OO$-estimate be positive or strictly positive.

## Examples

Big-O Estimate for Real Function/Examples

## Sources

- 1988: Dominic Welsh:
*Codes and Cryptography*... (previous) ... (next): Notation