PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (35)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: Low
Landau notation (Definition)

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

$\displaystyle 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
$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

$\displaystyle \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$.



"Landau notation" is owned by Mathprof. [ full author list (4) | owner history (3) ]
(view preamble)

View style:

See Also: lower bound for sorting

Other names:  O notation, omega notation, theta notation, big-O notation
Also defines:  big-o, small-o, small-omega
Keywords:  complexity, estimate, estimation, runtime complexity, space complexity

Attachments:
properties of $O$ and $o$ (Result) by paolini
formal definition of Landau notation (Definition) by paolini
$\sim$ is an equivalence relation (Result) by Wkbj79
Log in to rate this entry.
(view current ratings)

Cross-references: positive, algorithm, time complexity, logarithmic integral, conjecture, equivalent, Riemann hypothesis, equality, bounded, ratio, functions
There are 9 references to this entry.

This is version 15 of Landau notation, born on 2001-10-06, modified 2006-09-21.
Object id is 90, canonical name is LandauNotation.
Accessed 20799 times total.

Classification:
AMS MSC: 26A12 (Real functions :: Functions of one variable :: Rate of growth of functions, orders of infinity, slowly varying functions)
Pending Errata and Addenda
None.
[ View all 12 ]
Discussion
Style: Expand: Order:
forum policy
Which Landau? by igor on 2004-02-03 21:10:37
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?

[ reply | up ]
Interact
post | correct | update request | add derivation | add example | add (any)