# Definition:O Notation/Big-O Notation

## Contents

## Definition

**Big-O notation** occurs in a variety of contexts.

### Sequences

Let $\left \langle {a_n} \right \rangle$ and $\left \langle {b_n} \right \rangle$ be sequences of real or complex numbers.

**$a_n$ is big-O of $b_n$** if and only if

- $\exists c \in \R: c \ge 0 : \exists n_0 \in \N : \left({n \ge n_0 \implies \left\vert{a_n}\right\vert \le c \cdot \left\vert{b_n}\right\vert}\right)$

That is:

- $\left\vert{a_n}\right\vert \le c \cdot \left\vert{b_n}\right\vert$

for all sufficiently large $n$.

### Real Analysis

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

### Complex Analysis

Let $f$ and $g$ be complex functions defined for all complex numbers whose modulus is sufficiently large.

The statement:

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

is equivalent to:

- $\displaystyle \exists c\in \R: c\ge 0 : \exists r_0 \in \R : \forall z \in \C : (|z| \geq r_0 \implies |f(z)| \leq c \cdot |g(z)|)$

That is:

- $|f(z)| \leq c \cdot |g(z)|$

for all $z$ in a neighborhood of infinity in $\CC$.

### General Definition

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.

## Dependence on Parameters

Let $X$ 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\cup\{\infty\}$.

Let $A$ be a set.

Let $X_\alpha$ be a subset of $X$ for every $\alpha \in A$, which, if $x_0\neq\infty$, contains $x_0$.

Let $f_\alpha : X_\alpha\setminus \{x_0\} \to V$ be a function for every $\alpha \in A$.

Let $g : X \to V$ be a function.

The statement:

- $f_\alpha = O_\alpha(g)$ as $x \to x_0$

is equivalent to:

- $\forall \alpha \in A : f_\alpha = O(g)$ as $x \to x_0$

The $O$-estimate is said to be **independent** of $\alpha \in A$ if:

- There exists a neighborhood $U$ of $x_0$ in $X$ such that $\displaystyle \exists c\in \R: c\ge 0 : \forall \alpha \in A : \forall x\in (U\setminus\{x_0\}) \cap X_\alpha : \Vert f_\alpha(x)\Vert \leq c\cdot\Vert g(x)\Vert$

That is, if the implied constant and implied neighborhood can be chosen the same for all $\alpha \in A$.

## Uniform Estimates

Let $X$ be a set.

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

Then **$f$ is big O of $g$ uniformly** if and only if:

- $\exists c>0 : \forall x \in X : \Vert f(x) \Vert \leq c \cdot \Vert g(x) \Vert$

This is denoted: $f=O(g)$.

## Implied Constant

From the definition of the limit of a function, it can be seen that this is also equivalent to:

- $\exists c \in \R: c > 0, k \ge 0: \forall n > k, f \left({n}\right) \le c g \left({n}\right)$

For some fixed $k$ (appropriate to the function under consideration) the infimum of such $c$ is called the **implied constant**.

## Also denoted as

In analytic number theory, sometimes **Vinogradov's notations** $f \ll g$ or $g \gg f$ are used to mean $f = \mathcal O \left({g}\right)$.

This is clearer for estimates leading to typographically complex error terms.

Some sources use an ordinary $O$:

- $f = O \left({g}\right)$

## Also defined as

Some authors require that the inequality be valid on the entire domain of definition.

On $\mathsf{Pr} \infty \mathsf{fWiki}$, this is known as a uniform big-O estimate.

The statement $f = \map \OO g$ is sometimes seen to be defined as:

- $\displaystyle \exists \alpha \in \R: \alpha \ge 0 : \lim_{x \mathop \to \infty} \frac {\map f x} {\map g x} = \alpha$

However, requiring that the limit exists is too restrictive.

## Also see

- Results about
**asymptotic notations**can be found here.

## Sources

- 1932: A.E. Ingham:
*The Distribution of Prime Numbers*: $\S 1.1$ - 1994: H.E. Rose:
*A Course in Number Theory*(2nd ed.) ... (previous) ... (next): Preface to first edition: Prerequisites