Note: in the following, we assume that all functions map from a
totally ordered set to the reals. Usually when
discussing big-oh notation, functions map from nonnegative integers
to nonnegative integers or from nonnegative integers to nonnegative
reals, but the following defintions are more general.
A function f is O(g) iff there exist a nonzero constant M and a constant N such that, for every n > N, |f(n)| <= |Mg(n)|. Exercise: let P be a totally ordered set
with a greatest element m, and let f, g be functions from P to R such that g(m) != 0. Prove that f is O(g).
Notice that this is a weak bound. For example, f(x) = x2+7 may be said to be O(x2), but it may also be said to be O(x3) or O(ex).
Change <= to < in the above, and you have little-oh notation. Change <= to >=, and you have big-omega notation. Change <= to >, and you have little-omega notation.
There is also big-theta notation. f is Θ(g) iff there exist nonzero constants M1 and M2 and a constant N such that, for every n > N, |M1g(n)| <= |f(n)| <= |M2g(n)|. This is a stricter version of big-oh and big-omega notation. f is Θ(g) iff f is both O(g) and Ω(g).
One may use the above to define a relation: f ~ g iff f is Θ(g). It is easy to show that ~ is reflexive, symmetric, and transitive. Thus it is an equivalence relation, and partitions the set of functions into a number of equivalence classes. We call these complexity classes; the complexity class containing f is called Θ(f). Then we can say things like f ∈ Θ(g), which can make definitions and proofs simpler to write in some cases.
Important classes for real-valued functions of one integer variable: