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$)
[Math] Functions between polynomial and exponential
asymptotics
Best Answer
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$.