# Orders of Growth between Polynomial and Exponential

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.

-
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

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 "sub-exponentials," which grow as $e^\phi$ where $\lim\limits_{x\to \infty}\frac{\phi(x)}{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.

http://mathoverflow.net/questions/45477/closed-form-functions-with-half-exponential-growth

-
Where you write "One has also the 'sup-exponentials'"... do you mean sub-exponential? I ask because you use the latter term later. – Alex Reinking Jun 5 at 21:32
I think I have two typos here. – Kevin Carlson Jun 6 at 1:18