What is the most common definition of a subexponential growing function ? It seems there are different notions in literature.
Subexponential growing functions
8
$\begingroup$
functions
definition
-
3The usage varies a lot, but I have seen $O(2^{x^{\delta}})$ for any $\delta < 1$ being referred to subexponential. – 2011-09-15
-
0Yes I have also seen this and also the one given by Steven definition. – 2011-09-15
-
1https://cs.stackexchange.com/q/9813#9814 – 2017-05-16
1 Answers
8
I'd say that the most common one I see (and I should note that this is generally in the world of complexity theory/algorithm analysis) is a definition that distinguishes a subexponential function $f$ from exponential functions above it and polynomial functions below it, and moreover distinguishes it from 'polynomially diminished' exponential functions like $x^{-2}e^x$; that is, $f$ is subexponential means both that $\lim_{x\rightarrow\infty}f(x)x^{-\alpha}=\infty$ for all $\alpha$, and $\lim_{x\rightarrow\infty}(\log f(x))/x=0$ (which is a stronger condition than requiring that $\lim_{x\rightarrow\infty}f(x)\beta^{-x} = 0$ for all $\beta\gt1$).
-
0Could you possibly give examples of functions that satisfy one of these three conditions but not the other two? – 2018-08-31