# Landau notation

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

 $f=O(g)$

means that the ratio $\displaystyle\frac{f(x)}{g(x)}$ stays bounded as $x\to\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=\Omega(g)$

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

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

One more notational convention in this group is

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

meaning $\displaystyle\lim_{x\to\infty}\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)=\operatorname{li}x+O(\sqrt{x}\log x),$

where $\operatorname{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(Ax^{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