0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – greybeard
    Mar 3 at 9:51

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.