PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
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 $$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$ .




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

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, analysis, equality, bounded, ratio, functions
There are 15 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 24838 times total.

Classification:
AMS MSC26A12 (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)