Category:Big-O Notation

This category contains results about big-$\OO$ notation.
Definitions specific to this category can be found in Definitions/Big-O Notation.

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.