Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
Aagh! I was just about to post that! :) :) :) Hee-hee... –  mike4ty4 Dec 8 '12 at 1:18
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.