# Functions between polynomial and exponential

Does there exist a function $f(n)$ such that as $n \rightarrow \infty$, we have $p(n) < f(n) < e(n)$? Where $p$ is any polynomial and $e$ is any exponential (e.g. $e(n) = e^{\alpha n}, \alpha > 0$)

-
An important class of such functions arises in algorithmic complexity, en.wikipedia.org/wiki/L-notation – user51427 Dec 8 '12 at 1:20

Sure. The clearest way to see this is to take logarithms: after taking logarithms, you're looking for a function $\log f(n)$ which grows strictly faster than $k \log n$ for any $k$ but strictly slower than $kn$ for any $k$. And there are plenty of functions with this property, e.g. $(\log n)^{\alpha}$ for $\alpha > 1$ or $n^{\alpha}$ for $0 < \alpha < 1$.
How about $f(n)=e^{\sqrt{n}}$, slowing down the exponent in $e^n$? Or $f(n)=n^{\log{n}}$, speeding up the exponent in $n^k$?
Qiaochu beat you both but deleted his comment. :) One more note is that lots of people define exponential to be of form $e^{n^\alpha}$, for $\alpha > 0$. So $e^{\sqrt{n}}$ wouldn't work and you'd want something like $e^{(\log n)^2}$. But you're correct for the definition I gave. – StuartHa Dec 8 '12 at 1:21
If lots of people would define $e^{n^{\alpha}}$ to be an "exponential" function of $n$, then I would have to argue with lots of people on linguistics and semantics. – alex.jordan Dec 8 '12 at 1:34