Assume $F(n)$ is a positive function. If $F$ is growing faster than a polynomial then is it growing exponentially fast? Is this statement true?
Can we find a function $F(n)$ such that $$\frac{n^k}{F(n)}\to0$$ for all $k>0$ but such that $$\frac{F(n)}{e^{kn}}\to0$$ for all $k>0$?
I tried searching for this but all the answers are vague, so I wanted to know if anyone knows of such a function .
Best Answer
Exponential growth in computer science usually means $\Omega(e^{p(n)})$ where $p(n)$ is a polynomial that tends to infinity as $n$ becomes large. For something strictly in between $\Theta(p(n))$ for some polynomial $p$ and $\Theta(e^{p(n)})$ for some polynomial $p$, consider for example $e^{\sqrt{n}}$. This will also satisfy your limit conditions for any $k > 0$, which can be shown using tools like L'Hopital's rule.