Approximations and expansions Definition

Big O notation

Definition

Let $f$ and $g$ be real functions defined on an interval $[x_0, \infty)$ . The notation $f(x) = O(g(x))$ as $x \to \infty$ means that there are real numbers $C > 0$ and $x_1 \ge x_0$ with $|f(x)| \le C |g(x)| \quad \text{for all } x \ge x_1.$

Remarks

The same definition works as $x \to a$ , with $|x - a| < \delta$ in place of $x \ge x_1$ . If $g(x) \ne 0$ for large $x$ , then $f = O(g)$ means that $f/g$ is bounded for large $x$ . For example, $3x^2 + 5x = O(x^2)$ as $x \to \infty$ . Mathlib defines it for filters, as Asymptotics.IsBigO.

Tag	`0RYTGBJAGN`
URI	`m2://0RYTGBJAGN`
Aliases	`landau-big-o`
Kind	definition
Writing	W1 stated
MSC	41A60
Defines	Big O notation

Big O notation

Definition

Remarks

Where this leads

Further reading

What this page needs for W2

What links here

Used by