# Subexponential growing functions

What is the most common definition of a subexponential growing function ? It seems there are different notions in literature.

-
The usage varies a lot, but I have seen $O(2^{x^{\delta}})$ for any $\delta < 1$ being referred to subexponential. –  Srivatsan Sep 15 '11 at 19:49
Yes I have also seen this and also the one given by Steven definition. –  Mustafa Gokhan Benli Sep 15 '11 at 20:02

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$).
This can mean either that $f(x)\leqslant\exp(x^a)$ for $x$ large enough, for every positive $a$, or that $f(x)\leqslant\exp(ax)$ for $x$ large enough, for every positive $a$.
For functions such that $f(x)\to+\infty$ when $x\to+\infty$, the first condition means that $\log\log f(x)=o(\log x)$. The second one is more relaxed and asks only that $\log f(x)=o(x)$. Both seem to be used, see here.