Asymptotic Notation

This guide will introduce how to formally prove asymptotic relationships. See begriffs’ introduction of asymptotics if you’re a little rusty.

When we write computer programs, we need a way to describe the relative performance of different algorithms. We need to do so in a way that is machine independent and ignores irrelevant factors.1 Asymptotic notation is a short description of an algorithm’s performance as a function of its input. It is a convenient and mathematically precise notation. All computer scientists describe algorithms in terms of asymptotic performance.

Five symbols2 characterise the relationship between functions: ω, Ω, Θ, O, o. The asymptotic symbols are comparable to >, , =, , < respectively. The difference between numeric and asymptotic relationships are that asymptotic symbols describe the limiting relationship as inputs grow in size. Given below is a table summarizing the asymptotic relationships.

ω|f(n)|M|g(n)| for all M
Ω(0,]|f(n)|M|g(n)| for some M
Θ(0,)M1g(n)f(n)M2g(n) for some M1, M2
O[0,)|f(n)|M|g(n)| for some M
o0|f(n)|M|g(n)| for all M

Let’s take the most popular symbol, O, and prove f(n)O(g(n)) for some functions f(n) and g(n). We can approach the proof in a number of ways.

Method. The most formal method is using the scalar multiple definition.

  1. Identify the inequality associated with the asymptotic symbol.
  2. Substitute the function bodies.
  3. Attempt different values for M until the relationship holds for some input n0.
  4. Verify that the inequality stays true for all numbers greater than n0.

Example. Prove that f(n)O(g(n)) where f(n)=4n2+3n+2 and g(n)=2n2+n.

  1. In the table we see the inequality associated with O is |f(n)|M|g(n)|.
  2. We use the given information to get: |4n2+3n+2|M|2n2+n|.
  3. Try different values for M.
    1. Let M=1. Is |4n2+3n+2||2n2+n|? This seems unlikely given the coefficient on the high-order term is greater in 4n2+3n+2.
    2. Let M=2. Is |4n2+3n+2|2|2n2+n|? Now the high-order coefficients are both 4, but the expression 4n2+3n+2 still has a larger second-order term.
    3. Let M=3. Is |4n2+3n+2|3|2n2+n|? This seems more promising. Given n0=0, 4(0)2+3(0)+23(2)(0)2+3(0)20 which does not hold. However, given n0=1, 4(1)2+3(1)+23(2)(1)2+3(1)99. The inequality holds for this choice of n0.
  4. Can we show |4n2+3n+2|3|2n2+n| for all n1? We remove the absolute values because the functions are monotonically increasing at the points in question. 4n2+3n+26n2+3n22n2n21. Since the square of n is larger than 1 for all n1, the inequality holds.

Method. There is an alternate method I found more intuitive. This is the limit method.

  1. Consider the limnf(n)g(n).
  2. Substitute the function bodies.
  3. Evaluate the limit in any way possible, for example, using properties of the limit, reduction to known limits, or L’Hôpital’s rule3.
  4. Verify that the result of the limit is within the range of the asymptotic symbol.

Example. Prove that f(n)O(g(n)) where f(n)=n2 and g(n)=en.

  1. We have the limnf(n)g(n).
  2. We use the given information to get: limnn2en.
  3. We apply L’Hopital’s rule because the limit gives an indeterminate form : limn2nen. We apply it again: limn2en. The numerator is constant while the denominator monotonically increases. The limit is therefore 0.
  4. We see the interval associated with O from the symbol table is [0,). The value 0 is within the interval so the relationship holds.