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

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.

• I have one problem with this post's use of faster and slower: Given the context of time-complexity, does it refer to getting a result/completing an algorithm faster or slower? Or does it refer to something else? Commented Mar 3 at 9:51

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