# Definition:Big-O Notation

This page has been identified as a candidate for refactoring of advanced complexity.In particular: There is a great deal of merging of a number of concepts under one parent page, which could do with being reviewed.Until this has been finished, please leave
`{{Refactor}}` in the code.
Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Refactor}}` from the code. |

## Definition

### Sequences

Let $g: \N \to \R$ be a real sequence, expressed here as a real-valued function on the set of natural numbers $\N$.

Then $\map \OO g$ is defined as:

- $\map \OO g = \set {f: \N \to \R: \exists c \in \R_{>0}: \exists n_0 \in \N: \forall n > n_0: 0 \le \size {\map f n} \le c \cdot \size {\map g n} }$

### Real Analysis

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

### Complex Analysis

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

The statement:

- $\map f z = \map \OO {\map g z}$ as $\cmod z \to \infty$

is equivalent to:

- $\exists c \in \R_{\ge 0}: \exists r_0 \in \R: \forall z \in \C: \paren {\cmod z \ge r_0 \implies \cmod {\map f z} \le c \cdot \cmod {\map g z} }$

That is:

- $\cmod {\map f z} \le c \cdot \cmod {\map g z}$

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

### General Definition

Let $\struct {X, \tau}$ be a topological space.

Let $V$ be a normed vector space over $\R$ or $\C$ with norm $\norm {\,\cdot\,}$.

Let $f, g : X \to V$ be functions.

The statement:

- $\map f x = \map \OO {\map g x}$ as $x \to \infty$

is equivalent to:

- There exists a neighborhood of infinity $U \subset X$ such that:
- $\exists c \in {\R}_{\ge 0}: \forall x \in U: \norm {\map f x} \le c \norm {\map g x}$

That is:

- $\norm {\map f x} \le c \norm {\map g x}$

for all $x$ in a neighborhood of infinity.

## Uniform Estimates

Let $X$ be a set.

Let $V$ be a normed vector space over $\R$ or $\C$ with norm $\norm {\, \cdot \,}$.

Let $f, g : X \to V$ be mappings.

Then **$f$ is big-$\OO$ of $g$ uniformly** if and only if:

- $\exists c > 0 : \forall x \in X : \norm {\map f x} \le c \cdot \norm {\map g x}$

This is denoted:

- $f = \map \OO 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: \map f n \le c \map g n$

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

## 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 inequality be valid on the entire domain of definition.

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

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

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

However, requiring that the limit exists is generally viewed to be too restrictive.

## Also see

- Results about
**big-$\OO$ notation**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 - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next): Entry:**order notation**