Is $O(n^{f(n)})$ superexponential if $f(n)$ is a polynomial function such that $f(n) > n$ as $n$ approaches $\infty$?

Question

I know that exponential time complexity is $ O(k^n) $, where $k$ is some constant and $n$ is the input size, and that subexponential time is anything slower than that, $o(k^n)$ . If we define superexponential time complexity as anything faster than exponential time, $\omega(k^n)$, and given $O(n^{f(n)})$, where $f(n)$ is a polynomial function such that $f(n) > n$ as $n$ approaches $\infty$, would that be superexponential time complexity?

I guess what I'm more generally asking is, in $ O(k^n) $, does $n$ need to be just the input size $n$ or can it be $f(n)$ for time complexity to still be considered exponential?

I presume it would since I know that in algorithms such as the quadratic sieve whose time complexity is $O(exp(f(n)))$, where $f(n)$ < $n$ as $n$ approaches $\infty$, the time complexity is subexponential.

Answer 1

Exponential time is often described as complexity in $\mathcal{O}(2^{p(n)})$ for a polynomial function $p$ rather than $\mathcal{O}(k^n)$. See here for some references.

What you describe is the complexity of the class $\mathsf{E}$.

Nevertheless, using your definitions, if $f$ is a polynomial function greater than $n$, then $n^{f(n)}$ is indeed superpolynomial.

Since $f(n) > n$ at infinity, that means that $f(n) = an^d + g(n)$, with $d\geqslant 1$ and $g(n) =o(n^d)$.

Therefore, for any $k\in \mathbb{N}$: $$\frac{n^{f(n)}}{k^n} = \frac{2^{f(n)\log n}}{2^{n\log k}} = 2^{f(n)\log n - n\log k}\underset{n\rightarrow +\infty}{\longrightarrow}+\infty$$

This is because for $n$ big enough, $f(n)\log n - n\log k > n(\log n - \log k)$ and $k$ is a constant.

That means that $n^{f(n)}\notin \mathcal{O}(k^n)$.