4.2 Asymptotic function comparison

We discuss real valued functions defined on the positive integers.

Let f(n) and g(n) be two such functions.

• f(n) is dominated by g(n) [write f(n) = O(g(n))], if f(n)/g(n) is bounded above by a positive constant (not ∞).
• f(n) dominates g(n) [write f(n) = Ω(g(n))], if f(n)/g(n) is bounded below by a positive constant (not 0).
• f(n) and g(n) are codominant [write f(n) = Θ(g(n))], if both of the above.

Generally we compare a function of interest, such as the worst case run time T(n) of some algorithm on inputs of size n, to a leading term or leading monomial. This is a simple, easily remembered function that expresses most of what we need to know about T(n).

Function m(n) is a monomial if m(n) has the form lg(n)^a*n^b, for nonnegative constants a and b.

Function t(n) is a term if it is a constant times a monomial, t(n) = c*m(n). The constant c is called the coefficient of m(n) in t(n).

Given a function T(n) of interest (such as the worst case run time of an algorithm on inputs of size n), the leading term of T(n) is a term t(n) such that T(n)/t(n) → 1 as n → ∞

Given a function T(n) of interest, the leading monomial of T(n) is a monimial m(n) such that T(n)/m(n) → c as n → ∞, for some positive constant c. In other words, the leading monomial is the leading term with the constant coefficient removed.

A function has at most one leading monomial and at most one leading term.