Landau notation


Given two functionsMathworldPlanetmath f and g from + to +, the notation

f=O(g)

means that the ratio f(x)g(x) stays bounded as x. If moreover that ratio approaches zero, we write

f=o(g).

It is legitimate to write, say, 2x=O(x)=O(x2), 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(x2)=O(x).

The notation

f=Ω(g)

means that the ratio f(x)g(x) is bounded away from zero as x, or equivalently g=O(f).

If both f=O(g) and f=Ω(g), we write f=Θ(g).

One more notational convention in this group is

f(x)g(x),

meaning limxf(x)g(x)=1.

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

π(x)=lix+O(xlogx),

where lix denotes the logarithmic integralDlmfDlmfMathworldPlanetmathPlanetmath.

Landau notationMathworldPlanetmathPlanetmath 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(x3) steps, for example, without needing to specify exactly what is a step; for if f=O(x3), then f=O(Ax3) 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