4
$\begingroup$

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$)

  • 0
    An important class of such functions arises in algorithmic complexity, https://en.wikipedia.org/wiki/L-notation2012-12-08

2 Answers 2

9

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$.

4

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$?

  • 0
    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.2012-12-08