What can we say about the rate of growth of a function growing faster than all polynomials?

Question

Suppose $f: \mathbb{R} \rightarrow \mathbb{R}$ satisfies the following:

$$ \forall k \in \mathbb{N} \hspace{5pt} \lim_{t \rightarrow \infty} \frac{t^k}{f(t)} = 0.$$

Can we deduce a stronger growth rate for $f$? For instance (I know this is very hopeful - I am just giving an example of the sort of thing I mean) can we say

$$ \limsup_{t \rightarrow \infty} \frac{e^t}{f(t)} < \infty \hspace{5pt}?$$

Many thanks for your help.

Answer 1

If $g$ is any function that grows faster than all polynomials, then $\sqrt{g}$ is another such function, which grows slower than $g$. So nothing like your statement could ever be true, even if you replaced $e^t$ with some other function.

In general, growth rates of functions are extremely dense — given any two categories of growth rate where one is strictly larger than the other, you can just about always concoct a function whose growth is intermediate between them (except when your inability to do so is tautological; e.g., your categories are "polynomial functions" and "functions that grow faster than polynomials").

Answer 2

There isn't much you can say about the rate of growth of $f$. Specifically, there is no slowest $f$ that grows faster than any polynomial. For example, $x^{\log(x)}$, $x^{\log(\log(x))}$, $x^{\log(\log(\log(x)))}$, etc. all grow faster than any polynomial.

An equivalent characterization of your function is that $f\in x^{\omega(1)}$ where $\omega(1)$ means going to infinity. These functions are widely referenced in computer science as they are the functions describing the computational complexity of "inefficient" algorithms.