Lets take for example $\lim_{x\rightarrow\infty} \log(x)$, from a mathematical point of view this is $+\infty$, but from a logical point of view it's clear that $x$ converges to $+\infty$ much more quickly than $\log(x)$. Is there any kind of mathematics which take this into account?
speed of convergence to infinity
-
2You can say that the function $f(x)$ converges faster to infinity than the function $g(x)$ if $\lim_{x\rightarrow \infty }\frac{f(x)}{g(x)}=\infty $ or equivalently $\lim_{x\rightarrow \infty }\frac{g(x)}{f(x)}=0$. – 2012-02-15
1 Answers
The big O notation (and its various siblings and cousins) used to classify the asymptotic growth rates of functions addresses this problem head on.
For your two examples $f(x)=x$ and $g(x)=\log x$, we say that $g(x)$ is $O(f(x))$ but $f(x)$ is not $O(g(x))$. The $O(\cdots)$ intuitively denotes "grows no quicker than" or "is eventually proportional to or smaller than". Formally $f(x)$ is $O(g(x))$ if there exists an $N$ and a constant $c>0$ such that $f(x)\le cg(x)$ for all $x>N$. This is equivalent to the limit-based comparison given by Américo Tavares in the comment about; the result is a partial order on the set of all functions from positive reals (or integers) to positive reals (or integers).
Such properties are intensively used, for example, in the study of algorithmic complexity, where the functions being compared are the running times (or resource usage) of computer programs as a function of the size of their input.
Incidentally, there's no good way to assign numbers to different asymptotic growth rates. A coarse first approximation would be to classify a function $f$ according to the infimum of the $b$'s such that it is $O(x^b)$. But it turns out that $x\mapsto x^b\log x$ has a growth rate strictly between $x^b$ and $x^{b+\varepsilon}$ for any $\varepsilon>0$ -- and there is an entire hierarchy of logarithmically differing growth rates in that gap, which would be lost if we reduced it all to being about the exponent $b$.
-
0Thanks for the precision. I'm looking at the free book [The Design of Approximation Algorithms](http://www.designofapproxalgs.com/download.php), actually I'm a beginner in this area. – 2019-01-25