Asymptotic Notation

This guide will introduce how to formally prove asymptotic relationships. It presupposes a basic knowledge of asymptotic notation. Minimally, you should be vaguely familiar with what O(n) or Θ(nlogn) means.

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 only difference between numerical and asymptotic relationships is the asymptotic symbols describe the limiting relationship as inputs grow in size.

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.

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.

Consider the following example: prove that f(n)O(g(n)) where f(n)=4n2+3n+2 and g(n)=2n2+n.

  1. In the symbol 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.

Using the limit definition

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

Consider the following 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.

Symbol table

ω|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