Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|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
up vote 2 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|cite|improve this answer

Your Answer


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.