Asymptotic comparison of functions: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| (33 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== One-dimensional case == | == One-dimensional case == | ||
Let <math>f:\mathbb{ | 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>: | ||
# <math>\mathcal{O}(f)</math> consists of all functions <math>g:\mathbb{ | # <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>; | ||
# <math>\Omega(f)</math> consists of all functions <math>g:\mathbb{ | # <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>; | ||
# <math>\Theta(f):=\mathcal{O}(f)\cap\Omega(f)</math>; | # <math>\Theta(f):=\mathcal{O}(f)\cap\Omega(f)</math>; | ||
# <math>o(f):=\mathcal{O}(f)\setminus\Theta(f)</math>. | # <math>o(f):=\mathcal{O}(f)\setminus\Theta(f)</math>. | ||
# <math>\omega(f):=\Omega(f)\setminus\Theta(f)</math>. | |||
'''Remark:''' This notation is usually called the '''[https://en.wikipedia.org/wiki/Big_O_notation big O notation]''' or '''asymptotic notation''' and is also known as the '''Landau symbols''' or '''Landau-Bachmann symbols'''. | |||
== Mathematical rules for asymptotic comparison == | == Mathematical rules for asymptotic comparison == | ||
Let <math>f,g,h:\mathbb{ | Let <math>f,g,h:\mathbb{R}\rightarrow\mathbb{R}^+_0</math> be three functions. | ||
# Anti-reflexivity: If <math>f\in\mathcal{O}(g)</math>, it is <math>g\in\Omega(f)</math>, and vice versa. | # Anti-reflexivity: If <math>f\in\mathcal{O}(g)</math>, it is <math>g\in\Omega(f)</math>, and vice versa. | ||
# 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>", and "<math> | # 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>". | ||
# It is <math>\mathcal{O}(f)\cup\mathcal{O}(g)\subseteq\mathcal{O}(f+g)</math>. | # It is <math>\mathcal{O}(f)\cup\mathcal{O}(g)\subseteq\mathcal{O}(f+g)</math>. | ||
# If <math>f\in\mathcal{O}(g)</math>, it is <math>\oplus(f+g)</math>, where "<math>\oplus</math>" is anyone of "<math>\mathcal{O}</math>", "<math>\Omega</math>", "<math>\Theta | # 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>". | ||
# It is <math>f\in\mathcal(g)</math> if, and only if, the | # It is <math>f\in\mathcal{O}(g)</math> if, and only if, the [http://en.wikipedia.org/wiki/Limit_superior_and_limit_inferior limit superior] of the series <math>f(n)/g(n)</math> for <math>n\rightarrow+\infty</math> is finite. | ||
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. | # 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. | ||
For <math>a,b\mathbb{R}</math>, <math>a,b>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>", and "<math> | # For <math>a,b\in\mathbb{R}</math>, <math>a,b>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>. | ||
For , , it is . | # For all <math>k,\ell\in\mathbb{R}</math>, <math>k<\ell</math>, it is <math>n^k\in o(n^\ell)</math>. | ||
For all , it is . | # For all <math>k\in\mathbb{R}^+</math>, it is <math>\log^k(n)\in o(n)</math>. | ||
For all | # For all <math>k,a\in\mathbb{R}</math>, <math>a>1</math>, it is <math>n^k\in o(a^n)</math>. | ||
For all , , it is . | # For all <math>a,b\in\mathbb{R}</math>, <math>1<a<b</math>, it is <math>a^n\in o(b^n)</math>. | ||
# For all <math>a\in\mathbb{R}</math>, <math>a>1</math>, it is <math>a^n\in o(n!)</math>. | |||
Comparison with specific functions | == Comparison with specific functions == | ||
A function | A function <math>f:\mathbb{R}\rightarrow\mathbb{R}^+_0</math> is said to be | ||
linear if ; | # '''linear''' if <math>f\in\Theta(n)</math>; | ||
quadratic if ; | # '''quadratic''' if <math>f\in\Theta(n^2)</math>; | ||
cubic if ; | # '''cubic''' if <math>f\in\Theta(n^3)</math>; | ||
logarithmic if ; | # '''logarithmic''' if <math>f\in\Theta(\log(n))</math>; | ||
"n-log-n" if ; | # '''"n-log-n"''' if <math>f\in\Theta(n\cdot\log(n))</math>; | ||
polynomial if there is a polynomial | # '''polynomial''' if there is a polynomial <math>p:\mathbb{R}\rightarrow\mathbb{R}</math> such that <math>f\in\mathcal{O}(p)</math>; | ||
subexponential if | # '''subexponential''' if <math>f\in o(a^n)</math> for every <math>a\in\mathbb{R}</math>, <math>a>1</math>; | ||
exponential if there are , , such that | # '''exponential''' if there are <math>a,b\in\mathbb{R}</math>, <math>a>b>1</math>, such that <math>f\in\mathcal{O}(a^n)</math> and <math>f\in\Omega(b^n)</math>; | ||
factorial if | # '''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". | |||
Let | == 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>: | |||
; | # <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>; | ||
. | # <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>; | ||
# <math>\Theta(f):=\mathcal{O}(f)\cap\Omega(f)</math>; | |||
# <math>o(f):=\mathcal{O}\setminus\Theta(f)</math>. | |||
# <math>\omega(f):=\Omega(f)\setminus\Theta(f)</math>. | |||
Latest revision as of 15:38, 10 May 2016
One-dimensional case
Let [math]\displaystyle{ f:\mathbb{R}\rightarrow\mathbb{R}^+_0 }[/math] be a function. The following sets (a.k.a. classes) of functions are defined for [math]\displaystyle{ f }[/math]:
- [math]\displaystyle{ \mathcal{O}(f) }[/math] consists of all functions [math]\displaystyle{ g:\mathbb{R}\rightarrow\mathbb{R}^+_0 }[/math] such that there are [math]\displaystyle{ N_g,\,c_g\in\mathbb{R} }[/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{R} }[/math];
- [math]\displaystyle{ \Omega(f) }[/math] consists of all functions [math]\displaystyle{ g:\mathbb{R}\rightarrow\mathbb{R}^+_0 }[/math] such that there are [math]\displaystyle{ N_g,\,c_g\in\mathbb{R} }[/math] that fulfill [math]\displaystyle{ g(n)\geq\frac{1}{c_g}\cdot f(n) }[/math] for all [math]\displaystyle{ n\geq N_g }[/math], [math]\displaystyle{ n\in\mathbb{R} }[/math];
- [math]\displaystyle{ \Theta(f):=\mathcal{O}(f)\cap\Omega(f) }[/math];
- [math]\displaystyle{ o(f):=\mathcal{O}(f)\setminus\Theta(f) }[/math].
- [math]\displaystyle{ \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]\displaystyle{ f,g,h:\mathbb{R}\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]", "[math]\displaystyle{ o }[/math]", and "[math]\displaystyle{ \omega }[/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)=\oplus(g) }[/math], where "[math]\displaystyle{ \oplus }[/math]" is anyone of "[math]\displaystyle{ \mathcal{O} }[/math]", "[math]\displaystyle{ \Omega }[/math]", and "[math]\displaystyle{ \Theta }[/math]".
- It is [math]\displaystyle{ f\in\mathcal{O}(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.
- 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\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]", "[math]\displaystyle{ o }[/math]", and "[math]\displaystyle{ \omega }[/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].
- 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].
- For all [math]\displaystyle{ k\in\mathbb{R}^+ }[/math], it is [math]\displaystyle{ \log^k(n)\in o(n) }[/math].
- 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].
- 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].
- 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{R}\rightarrow\mathbb{R}^+_0 }[/math] is said to be
- linear if [math]\displaystyle{ f\in\Theta(n) }[/math];
- quadratic if [math]\displaystyle{ f\in\Theta(n^2) }[/math];
- cubic if [math]\displaystyle{ f\in\Theta(n^3) }[/math];
- logarithmic if [math]\displaystyle{ f\in\Theta(\log(n)) }[/math];
- "n-log-n" if [math]\displaystyle{ f\in\Theta(n\cdot\log(n)) }[/math];
- polynomial if there is a polynomial [math]\displaystyle{ p:\mathbb{R}\rightarrow\mathbb{R} }[/math] such that [math]\displaystyle{ f\in\mathcal{O}(p) }[/math];
- 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];
- 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];
- 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{R} }[/math] and let [math]\displaystyle{ f:\mathbb{R}^k\rightarrow\mathbb{R}^+_0 }[/math]. 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{R}^k\rightarrow\mathbb{R}^+_0 }[/math] such that there are [math]\displaystyle{ N_g,\,c_g\in\mathbb{R} }[/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{R} }[/math] such that [math]\displaystyle{ n_1,\ldots,n_k\geq N_g }[/math];
- [math]\displaystyle{ \Omega(f) }[/math] consists of all functions [math]\displaystyle{ g:\mathbb{R}^k\rightarrow\mathbb{R}^+_0 }[/math] such that there are [math]\displaystyle{ N_g,\,c_g\in\mathbb{R} }[/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{R} }[/math] such that [math]\displaystyle{ n_1,\ldots,n_k\geq N_g }[/math];
- [math]\displaystyle{ \Theta(f):=\mathcal{O}(f)\cap\Omega(f) }[/math];
- [math]\displaystyle{ o(f):=\mathcal{O}\setminus\Theta(f) }[/math].
- [math]\displaystyle{ \omega(f):=\Omega(f)\setminus\Theta(f) }[/math].