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

  • 3
    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
  • 1
    cs.stackexchange.com/q/9813#9814 – Kaveh May 16 '17 at 16:34
up vote 8 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$).

  • Could you possibly give examples of functions that satisfy one of these three conditions but not the other two? – mathreader Aug 31 at 3:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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