Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 0 down vote accepted

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$).

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.