# Asymptotic comparison of functions

Jump to: navigation, search

## One-dimensional case

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

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

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 $f,g,h:\mathbb{R}\rightarrow\mathbb{R}^+_0$ be three functions.

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

## Comparison with specific functions

A function $f:\mathbb{R}\rightarrow\mathbb{R}^+_0$ is said to be

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

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

## Multidimensional case

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

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