Definitions
This page summarizes “big-O” notation and related notations introduced by Paul Bachmann and Edmund Landau. See also this page on big-O tilde notation.
Infinite limits
The notation f(x) = O( g(x) ) means the function f(x) is eventually bounded by a multiple of g(x). Here “eventually” depends on the direction in which one is taking a limit. We focus first on limits going to infinity since that is the most common case.
More precisely, we say f(x) = O( g(x) ) as x → ∞ if there exist positive constants M and C such that f(x) ≤ C g(x) for all x > M.
While “Big O” notation means “eventually bounded above by,” Ω notation means “eventually bounded below by.” More precisely, we say f(x) = Ω( g(x) ) as x → ∞ if there exist positive constants M and C such that f(x) ≥ C g(x) for all x > M.
The notation f(x) = Θ( g(x) ) means that f(x) = O( g(x) ) and f(x) = Ω( g(x) ).
There are two remaining notations: ο (Greek omicron) and ω (lower-case Greek omega). The omicron notation is also called “little-o” notation.
We say f(x) = ο( g(x) ) if the limit as x → ∞ of f(x)/g(x) is 0.
We say f(x) = ω( g(x) ) if the same limit is ∞.
Finite limits
The ideas above remain essentially the same for finite limits, though the technical details of the definitions differ.
f(x) = O( g(x) ) as x → k if there exist positive constants δ and C such that f(x) ≤ C g(x) for all x such that |x – k| < δ.
f(x) = Ω( g(x) ) as x → k if there exist positive constants δ and C such that f(x) ≥ C g(x) for all x such that |x – k| < δ.
f(x) = ο( g(x) ) as x → k if the limit as x → k of f(x)/g(x) is 0.
f(x) = ω( g(x) ) as x → k if the limit as x → k of f(x)/g(x) is ∞.
Often you will see statements such as f(x) = O( g(x) ) without reference to an explicit limit and will have to determine from context what limit is implied.
Usage
Big-O notation is common in computer science and mathematics. However, some of the other notations are common in one field but not in the other.
In computer science, the emphasis is nearly always on the behavior of an algorithm as the problem size n grows, and so limits are implicitly taken as n goes to infinity. The Ω and Θ notations are more commonly used in computer science than in mathematics. Little-o (omicron) notation is rarely used.
In mathematics, big-O notation is common with both infinite and finite limits. Little-o notation is the next most popular. The Ω and Θ notations are uncommon.
The notation f = ω( g(x) ) is not common in computer science or mathematics.
Reference
For further information, see Introduction to Algorithms (computer science) or Asymptotic Methods in Analysis (mathematics).