Asymptotic comparison of functions

From Algowiki
Jump to: navigation, search

One-dimensional case

Let [math]f:\mathbb{R}\rightarrow\mathbb{R}^+_0[/math] be a function. The following sets (a.k.a. classes) of functions are defined for [math]f[/math]:

  1. [math]\mathcal{O}(f)[/math] consists of all functions [math]g:\mathbb{R}\rightarrow\mathbb{R}^+_0[/math] such that there are [math]N_g,\,c_g\in\mathbb{R}[/math] that fulfill [math]g(n)\leq c_g\cdot f(n)[/math] for all [math]n\geq N_g[/math], [math]n\in\mathbb{R}[/math];
  2. [math]\Omega(f)[/math] consists of all functions [math]g:\mathbb{R}\rightarrow\mathbb{R}^+_0[/math] such that there are [math]N_g,\,c_g\in\mathbb{R}[/math] that fulfill [math]g(n)\geq\frac{1}{c_g}\cdot f(n)[/math] for all [math]n\geq N_g[/math], [math]n\in\mathbb{R}[/math];
  3. [math]\Theta(f):=\mathcal{O}(f)\cap\Omega(f)[/math];
  4. [math]o(f):=\mathcal{O}(f)\setminus\Theta(f)[/math].
  5. [math]\omega(f):=\Omega(f)\setminus\Theta(f)[/math].

Remark: This notation is usually called the big O notation or asymptotic notation and is also known as the Landau symbols or Landau-Bachmann symbols.

Mathematical rules for asymptotic comparison

Let [math]f,g,h:\mathbb{R}\rightarrow\mathbb{R}^+_0[/math] be three functions.

  1. Anti-reflexivity: If [math]f\in\mathcal{O}(g)[/math], it is [math]g\in\Omega(f)[/math], and vice versa.
  2. Transitivity: If [math]f\in\oplus(g)[/math] and [math]g\in\oplus(h)[/math] then [math]f\in\oplus(h)[/math], where "[math]\oplus[/math]" is anyone of "[math]\mathcal{O}[/math]", "[math]\Omega[/math]", "[math]\Theta[/math]", "[math]o[/math]", and "[math]\omega[/math]".
  3. It is [math]\mathcal{O}(f)\cup\mathcal{O}(g)\subseteq\mathcal{O}(f+g)[/math].
  4. If [math]f\in\mathcal{O}(g)[/math], it is [math]\oplus(f+g)=\oplus(g)[/math], where "[math]\oplus[/math]" is anyone of "[math]\mathcal{O}[/math]", "[math]\Omega[/math]", and "[math]\Theta[/math]".
  5. It is [math]f\in\mathcal{O}(g)[/math] if, and only if, the limit superior of the series [math]f(n)/g(n)[/math] for [math]n\rightarrow+\infty[/math] is finite.
  6. It is [math]f\in o(g)[/math] if, and only if, this limit superior is zero. Note that, due to nonnegativity, this is equivalent to the statement that [math]\lim_{n\rightarrow+\infty}f(n)/g(n)[/math] exists and equals zero.
  7. For [math]a,b\in\mathbb{R}[/math], [math]a,b\gt 1[/math], it is [math]\oplus(\log_a(n))=\oplus(\log_b(n))[/math], where "[math]\oplus[/math]" is anyone of "[math]\mathcal{O}[/math]", "[math]\Omega[/math]", "[math]\Theta[/math]", "[math]o[/math]", and "[math]\omega[/math]" (follows immediately from the basic rule [math]\log_a(n)/\log_b(n)=\log_a(b)=[/math] const). In particular, the base of a logarithm function may be omitted: [math]\oplus(\log(n))=\oplus(\log_a(n))[/math].
  8. For all [math]k,\ell\in\mathbb{R}[/math], [math]k\lt \ell[/math], it is [math]n^k\in o(n^\ell)[/math].
  9. For all [math]k\in\mathbb{R}^+[/math], it is [math]\log^k(n)\in o(n)[/math].
  10. For all [math]k,a\in\mathbb{R}[/math], [math]a\gt 1[/math], it is [math]n^k\in o(a^n)[/math].
  11. For all [math]a,b\in\mathbb{R}[/math], [math]1\lt a\lt b[/math], it is [math]a^n\in o(b^n)[/math].
  12. For all [math]a\in\mathbb{R}[/math], [math]a\gt 1[/math], it is [math]a^n\in o(n!)[/math].

Comparison with specific functions

A function [math]f:\mathbb{R}\rightarrow\mathbb{R}^+_0[/math] is said to be

  1. linear if [math]f\in\Theta(n)[/math];
  2. quadratic if [math]f\in\Theta(n^2)[/math];
  3. cubic if [math]f\in\Theta(n^3)[/math];
  4. logarithmic if [math]f\in\Theta(\log(n))[/math];
  5. "n-log-n" if [math]f\in\Theta(n\cdot\log(n))[/math];
  6. polynomial if there is a polynomial [math]p:\mathbb{R}\rightarrow\mathbb{R}[/math] such that [math]f\in\mathcal{O}(p)[/math];
  7. subexponential if [math]f\in o(a^n)[/math] for every [math]a\in\mathbb{R}[/math], [math]a\gt 1[/math];
  8. exponential if there are [math]a,b\in\mathbb{R}[/math], [math]a\gt b\gt 1[/math], such that [math]f\in\mathcal{O}(a^n)[/math] and [math]f\in\Omega(b^n)[/math];
  9. factorial if [math]f\in\Theta(n!)[/math].

Remark: Note that the notion of polynomial is based on an "[math]\mathcal{O}[/math]", not on a "[math]\Theta[/math]". In fact, in this context, "polynomial" is usually used short for "polynomially bounded from above".

Multidimensional case

Let [math]k\in\mathbb{R}[/math] and let [math]f:\mathbb{R}^k\rightarrow\mathbb{R}^+_0[/math]. The following sets (a.k.a. classes) are defined for [math]f[/math]:

  1. [math]\mathcal{O}(f)[/math] consists of all functions [math]g:\mathbb{R}^k\rightarrow\mathbb{R}^+_0[/math] such that there are [math]N_g,\,c_g\in\mathbb{R}[/math] that fulfill [math]g(n_1,\ldots,n_k)\leq c_g\cdot f(n_1,\ldots,n_k)[/math] for all [math]n_1,\ldots,n_k\in\mathbb{R}[/math] such that [math]n_1,\ldots,n_k\geq N_g[/math];
  2. [math]\Omega(f)[/math] consists of all functions [math]g:\mathbb{R}^k\rightarrow\mathbb{R}^+_0[/math] such that there are [math]N_g,\,c_g\in\mathbb{R}[/math] that fulfill [math]g(n_1,\ldots,n_k)\geq c_g\cdot f(n_1,\ldots,n_k)[/math] for all [math]n_1,\ldots,n_k\in\mathbb{R}[/math] such that [math]n_1,\ldots,n_k\geq N_g[/math];
  3. [math]\Theta(f):=\mathcal{O}(f)\cap\Omega(f)[/math];
  4. [math]o(f):=\mathcal{O}\setminus\Theta(f)[/math].
  5. [math]\omega(f):=\Omega(f)\setminus\Theta(f)[/math].