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:

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

is equivalent to:

$\exists c \in \R: c \ge 0: \exists x_0 \in \R : \forall x \in \R : \left({x \ge x_0 \implies \left\vert{f \left({x}\right)}\right\vert \le c \cdot \left\vert{g \left({x}\right)}\right\vert}\right)$


That is:

$\left\vert{f \left({x}\right)}\right\vert \le c \cdot \left\vert{g \left({x}\right)}\right\vert$

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 $g \left({x}\right)$ be nonzero for $x$ sufficiently large.