Landau notation

Given two functions $f$ and $g$ from ${ℝ}^{+}$ to ${ℝ}^{+}$, the notation

$$f=O(g)$$

means that the ratio ${\displaystyle \frac{f(x)}{g(x)}}$ stays bounded as $x\to \mathrm{\infty }$. If moreover that ratio approaches zero, we write

$$f=o(g).$$

It is legitimate to write, say, $2x=O(x)=O(x^2)$, with the understanding that we are using the equality sign in an unsymmetric (and informal) way, in that we do not have, for example, $O(x^2)=O(x)$.

The notation

$$f=\mathrm{\Omega }(g)$$

means that the ratio ${\displaystyle \frac{f(x)}{g(x)}}$ is bounded away from zero as $x\to \mathrm{\infty }$, or equivalently $g=O(f)$.

If both $f=O(g)$ and $f=\mathrm{\Omega }(g)$, we write $f=\mathrm{\Theta }(g)$.

One more notational convention in this group is

$$f(x)\sim g(x),$$

meaning $\underset{x\to \mathrm{\infty }}{lim}{\displaystyle \frac{f(x)}{g(x)}}=1$.

In analysis, such notation is useful in describing error estimates (http://planetmath.org/AsymptoticEstimate). For example, the Riemann hypothesis is equivalent to the conjecture

$$\pi (x)=\mathrm{li}x+O(\sqrt{x}\log x),$$

where $\mathrm{li}x$ denotes the logarithmic integral.

Landau notation is also handy in applied mathematics, e.g. in describing the time complexity of an algorithm. It is common to say that an algorithm requires $O(x^3)$ steps, for example, without needing to specify exactly what is a step; for if $f=O(x^3)$, then $f=O(A{x}^3)$ for any positive constant $A$.

Title	Landau notation
Canonical name	LandauNotation
Date of creation	2013-03-22 11:42:56
Last modified on	2013-03-22 11:42:56
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	28
Author	Mathprof (13753)
Entry type	Definition
Classification	msc 26A12
Classification	msc 20H15
Classification	msc 20B30
Synonym	O notation
Synonym	omega notation
Synonym	theta notation
Synonym	big-O notation
Related topic	LowerBoundForSorting
Related topic	ConvergenceOfIntegrals
Defines	big-o
Defines	small-o
Defines	small-omega