Asymptotic Analysis

Big Oh · Ο

defines an Upper bound
f(n) is Ο( g(n) ) iff constants k, and c exist such that for all n > k, c*f(n) >= g(n)
To be useful we want the smallest function that meets the requirement.
In general, for polynomial functions, one can set f(n) to be
the largest term in g(n) and select k and c by taking the
largest coefficients of g(n)

Omega · Ω

defines a lower bound
f(n) is Ω( g(n) ) iff exist constants k, and c such that c*f(n) <= g(n) for all n > k
To be useful we want the largest function that meets the requirement.
In general, for polynomial functions (where all terms are positive), one can set f(n) to be the largest term in g(n) and select k = c = 1

Theta · Θ

defines a tight bound
f(n) is Θ ( g(n) ) iff f(n)

( Ο( g(n) )

Ω( g(n) ) )
This is the gold standard.

Looser bounds also exist in the literature

Little oh · ο

defines an Upper bound
f(n) is ο( g(n) ) iff f(n) is Ο( g(n) ) but g(n) is not Ω( f(n) )
Or more simply
ο(g(n)) = Ο(g(n)) - Ω(g(n))

Little omega · ω

defines a lower bound
f(n) is ω( g(n) ) iff f(n) is Ω( g(n) ) but g(n) is not Θ( f(n) )
Or more simply
ω(g(n)) = Ω(g(n)) - Ο(g(n))
or even
ω(g(n)) = Ω(g(n)) - Θ(g(n))

Useful Links

http://www.nist.gov/dads/HTML/bigOnotation.html
http://www.nist.gov/dads/HTML/theta.html
http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html
http://www.fredosaurus.com/notes-cpp/algorithms/big-oh/bigoh.html