Orders of Growth between Polynomial and Exponential

Solution 1:

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.

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