Source: cirosantilli/big-o-notation
= Big O notation
{title2=$O(n)$}
{wiki}
Module bound above, possibly multiplied by a constant:
$$
f(x) = O(g(x))
$$
is defined as:
$$
\exists M > 0 \exists x_0 \forall x > x_0 \colon |f(x)| \leq M g(x)
$$
E.g.:
* $\forall c \in \R x + c = O(x)$. For $c < 0$, $M = 1$ is enough. Otherwise, any $M > 1$ will do, the bottom line will always catch up to the top one eventually.