Bachmann-Landau Asymptotic Notation

(This article looks technical, although it is really not. I overuse mathematical symbols if only to exercise a newly found way to display \TeX within HTML. Other people may prefer to discuss asymptotic notation in a much more concrete way.)

According to Donald Knuth, asymptotic notation was invented by Paul Bachmann and popularized by Edmund Landau (both were mathematicians). It is a commonly used method for studying how an algorithm scales with input sizes or input complexity. We will now get some general definitions out of the way.

Since we will be speaking of sets of functions, we will use the set theory notation for these (given with respect to domains and ranges). Suppose we have sets A and B. We define B^A to be the set of all functions having A as their domain and B as their range. This means that f \in B^A \iff f:A \to B.

Definition. Consider a real function f \in {\bf R}^{\bf R}. We define the “Big O of eff” as: O(f) = \{ g \in {\bf R}^{\bf R} : (\exists x_0 \in {\bf R} (\exists c \in {\bf R}_{>0} (\forall x>x_0(|g(x)| \le c|f(x)|)))) \}.

Definition. Consider a real function f \in {\bf R}^{\bf R}. We define the “Big Omega of eff” as: \Omega(f) = \{ g \in {\bf R}^{\bf R} : (\exists x_0 \in {\bf R} (\exists c \in {\bf R}_{>0} (\forall x>x_0(c|f(x)| \le |g(x)|)))) \}.
Definition. Consider a real function f \in {\bf R}^{\bf R}. We define the “Big Theta of eff” as: \Theta(f) = O(f) \cap \Omega(f).

(CLR prefers Big Theta, but DPV prefers Big O.)

In a way, Big O, Omega, and Theta can be seen as maps from {\bf R}^{\bf R} to the power set \cal{P}({\bf R^R}). There also exist the stronger “Small O” and “Small Omega” sets, but we will not be concerned with these.

We defined Big O, Omega, and Theta to be subsets of the set of real functions {\bf R}^{\bf R}. However, we may be concerned with functions other than real functions (perhaps even functions in multiple variables). We can opt for a more general definition of Big O, Omega, and Theta as long as our domain and range have linear orderings. In fact, we are often concerned with sets of functions whose domain is the naturals and whose range is the positive reals, i.e. {\bf R}_+^{\bf N}. Note that functions with different domains and ranges may not be order-comparable in the way we defined Big O, Omega, and Theta. So we must be careful to maintain the same domain and range for all the functions that we are interested in comparing.

If Big O were defined as a binary relation on the set {\bf R}^{\bf R}, then it would be reflexive, transitive, and antisymmetric (i.e. a partial ordering). Similarly, Big Omega as a binary relation would also be reflexive, transitive, and antisymmetric. Moreover, Big O and Omega are inverse relations since f \in O(g) \iff g \in \Omega (f). If Big Theta were defined as a binary relation, then it would be reflexive, symmetric, and transitive. Therefore, Big Theta forms an equivalence class of functions. Even though both Big O amd Omega relations have the possibility of strict set inclusion (e.g O(1) \subset O(x) \subset O(x^2) \subset O(x^3) \subset \cdots, this is not possible with Big Theta. Therefore, we have \Theta(f) \subseteq \Theta(g) \iff \Theta(f) = \Theta(g).

We are generally very lax when dealing with asymptotic notation. For example, it is (more) common to write O(f(x)) instead of O(f). It is also more common to write the function’s analytical expression within the Big Letter’s parentheses, e.g. if f(x)=x^2+2, then Big Omega of eff may be written as \Omega (x^2+2), which simplifies to \Omega (x^2). This abuse of notation is dangerous because there is no way to distinguish a function symbol and an independent variable symbol (just consider taking the Big O of a function such as x(t)=e^t). So general conventions restrict independent variables to the letters x, n, and t. If we see one of these letters within the parentheses of Big O, Omega, or Theta then we are dealing with the analytical expression for a function and not the function itself.

References

Cormen, T., Leiserson, C., and Rivest, R.  Introduction to Algorithms.

“Big O notation.” Wikipedia http://en.wikipedia.org/wiki/Big_O_notation.

This entry was posted in Algorithms, Computer Science. Bookmark the permalink.