Asymptotic comparison of functions: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 43: Line 43:


Let <math>k\in\mathbb{N}</math> and let <math>f:\mathbb{N}^k\rightarrow\mathbb{R}^+_0</math>. The following sets (a.k.a. '''classes''') are defined for <math>f</math>:
Let <math>k\in\mathbb{N}</math> and let <math>f:\mathbb{N}^k\rightarrow\mathbb{R}^+_0</math>. The following sets (a.k.a. '''classes''') are defined for <math>f</math>:
# <math>\mathcal{O}(f)</math> consists of all functions <math>g:\mathbb{N}^k\rightarrow\mathbb{R}^+_0</math> such that there are <math>N_g,\,c_g\in\mathbb{N}</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{N}</math> such that <math>n_1,\ldots,nk\geq N_g</math>;
# <math>\mathcal{O}(f)</math> consists of all functions <math>g:\mathbb{N}^k\rightarrow\mathbb{R}^+_0</math> such that there are <math>N_g,\,c_g\in\mathbb{N}</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{N}</math> such that <math>n_1,\ldots,n_k\geq N_g</math>;
 
# <math>\Omega(f)</math> consists of all functions <math>g:\mathbb{N}^k\rightarrow\mathbb{R}^+_0</math> such that there are <math>N_g,\,c_g\in\mathbb{N}</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{N}</math> such that <math>n_1,\ldots,n_k\geq N_g</math>;
;
;
.
.

Revision as of 09:25, 26 May 2015

http://huffmann.algo.informatik.tu-darmstadt.de/wiki/wiki.algo.informatik.tu-darmstadt.de/index.php/Asymptotic_comparison_of_functions.html

One-dimensional case

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

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

Mathematical rules for asymptotic comparison

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

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

Comparison with specific functions

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

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

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

Multidimensional case

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

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

.