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

From ProofWiki
Jump to navigation Jump to search

Definition

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


Also defined as

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