## You are here

HomeLandau notation

## Primary tabs

# 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. 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$.

## Mathematics Subject Classification

26A12*no label found*20H15

*no label found*20B30

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Which Landau?

I must say, I'm curious as to which Landau is this notation

named after. Is it the famous theoretical physicist Lev D. Landau?

or someone else?

## Re: Which Landau?

According to ``Concrete Mathematics'' by Donald Knuth, Oren Patashnik and Ronald Graham the Landau notation was invented by Paul Bachmann and widely used by Edmund Landau, a number theorist.