# Landau notation

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

$$f=O(g)$$ |

means that the ratio $\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 $\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}\mathrm{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 |