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 known in contemporary mathematics about orders of growth for functions that exceed any degree polynomial, but fall short of exponential? This is a subject for which I've found little literature in the past.

An example: $Ae^{a\sqrt x}$ clearly will outrun any finite degree polynomial, but will be outrun by $Be^{bx}$.

If we replace $x$ with $y^2$ then that example doesn't seem so deep. Are there functions that exceed polynomial growth yet fall short of $Ae^{ax^p}$ for any power $0<p<1$? What classes of functions can we distinguish with different kinds of in-between orders of growth? What can we know about their power series expansions, or behavior in the complex plane? Those are examples of the kinds of questions I have, and would like to find literature on.

Have any definitions or terminology been established concerning this? The right jargon will facilitate searching.

share|improve this question
I added the computational-complexity tag since that's such a locus of interest in questions like these. –  Kevin Carlson Nov 1 '12 at 8:24
add comment

1 Answer

up vote 3 down vote accepted

One of the best-known classes is the "quasi-polynomials", which are exponentials of polynomials in logs, e.g. $e^{\log^2(x)+\log x}$, which you might also write as $x^{\log(x)+1}$. As long as the degree of the exponent is greater than $1$, these fit between polynomial and exponential.

One has also the "sup-exponentials," which grow as $e^\phi$ where $\lim\limits_{x\to \infty}\frac{x}{\phi(x)}=0$. The most obvious examples that aren't quasi-polynomial are along the lines of the one you gave.

These don't exhaust the possibilities, though. You may be interested in a considerable volume of discussion over at MO of functions $f$ such that $f(f(x))$ is exponential.

These "half-exponentials" are in between the two classes I've described: a proper sub-exponential has an exponent that dominates all polynomials of logarithms, so its composition with itself has an exponent that dominates all polynomials-and thus isn't exponential. In the other direction, you can see that quasi-polynomials are closed under self-composition. Here's the latest thread, with links to others.


share|improve this answer
add comment

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.