Wikipedia talks about two groups of functions with asymptotic growth rates between polynomial and exponential – quasi-polynomial functions and sub-exponential functions.
It only gives two examples of such a function, however, and those functions are of the form $2^{(n^{1/3})}$ (the runtime of the prime field sieve) and $2^{(n \log n)^{1/2}}$ (the runtime of the graph isomorphism problem). Both of these functions have the property that $f(p(n))$ (where $p$ is some polynomial) is still a function in $\Omega(2^n)$.
Is there an example of a function that doesn't have this property? Specifically, in terms of growth behaviour, I want the following to be true for $f(n)$:
-
$f(n)$ grows faster than any polynomial function – that is, for any polynomial $p(n)$, $f \notin O(p(n))$.
-
No polynomial of $f(n)$ grows faster than an exponential function – that is, for any polynomial $p(n)$, a new function defined as $g(n) = f(p(n))$ is in $o(2^n)$.
Best Answer
Let $f(n) = n^{\log n}$. Then for any $k$ we have $$ \frac{n^k}{f(n)} = n^{k-\log n} \to 0 $$ that is $n^k \in o(f)$, any $k$.
Moreover, for any $k$ with $p_k(n)=n^k$, we have $$ f(p_k(n)) = f(n^k) = n^{k\log n^k} = n^{k^2\log n} = 2^{k^2\log^2 n}$$ which is $o(a^n)$ for any $a > 1$, as $a^n = 2^{n\log a}$.