Landau notation

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


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


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


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


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

In analysis, such notation is useful in describing error estimates ( For example, the Riemann hypothesisMathworldPlanetmath is equivalent to the conjecture


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