Asymptotic comparison of functions
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]:
- [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];
- [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];
- [math]\displaystyle{ \Theta(f):=\mathcal{O}(f)\cap\Omega(f) }[/math];
- [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.
- Anti-reflexivity: If [math]\displaystyle{ f\in\mathcal{O}(g) }[/math], it is [math]\displaystyle{ g\in\Omega(f) }[/math], and vice versa.
- 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]".
- It is [math]\displaystyle{ \mathcal{O}(f)\cup\mathcal{O}(g)\subseteq\mathcal{O}(f+g) }[/math]..
- If [math]\displaystyle{ f\in\mathcal{O}(g) }[/math], it is [math]\displaystyle{ \oplus(f+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]".
- It is [math]\displaystyle{ f\in\mathcal(g) }[/math] if, and only if, the [superior] of the series [math]\displaystyle{ f(n)/g(n) }[/math] for [math]\displaystyle{ n\rughtarrow+\infty }[/math] is finite.
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. For [math]\displaystyle{ a,b\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 const). In particular, the base of a logarithm function may be omitted: [math]\displaystyle{ \oplus(\log(n))=\oplus(\log_a(n)) }[/math]. For , , it is . For all , it is . For all and , , it is . For all , , it is . Known Related Topics Remark Reference
Comparison with specific functions
A function is said to be linear if ; quadratic if ; cubic if ; logarithmic if ; "n-log-n" if ; polynomial if there is a polynomial such that ; subexponential if for every , ; exponential if there are , , such that and ; factorial if . Known Related Topics Remark Note that the notion of polynomial is based on an "", not on a "". In fact, in this context, "polynomial" is usually used short for "polynomially bounded from above". Reference
Multidimensional case
Let and let . The following sets (a.k.a. classes) are defined for :
consists of all functions such that there are and that fulfill for all such that ; consists of all functions such that there are and that fulfill for all such that ;
.