5
$\begingroup$

I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity.

For instance, if an algorithm runs for $nC(n-1)$ steps, where $C(\cdot)$ is the Catalan number, is this algorithm super-exponential in $n$?

$\endgroup$
  • $\begingroup$ We discourage posts that simply state a question out of context, and expect the community to solve it. Can you provide a few urls or books where you have seen this "super-exponential"? Or do you want to initiate the usage of that term? $\endgroup$ – Apass.Jack Nov 12 '18 at 14:03
6
$\begingroup$

"Super-exponential" just means more than exponential, so a function is super-exponential if it grows faster than any exponential function. More formally, this means that it is $\omega(c^n)$ for every constant $c$, i.e., if $\lim_{n\to\infty} f(n)/c(n)=\infty$ for all constants $c$.

Conversely, a function is "sub-exponential" if it is $o(c^n)$ for every constant $c>1$, i.e., $\lim_{n\to\infty} f(n)/c(n)=\infty$ for all constants $c>1$.

Asymptotically, the $n$th Catalan number is $\Theta(4^n\, n^{-3/2})$. This is $o(4^n)$, so the Catalan numbers are not super-exponential; it is $\omega(2^n)$, so they're not subexponential either. The Catalan numbers are just exponential.

An exception to the above definitions is that, in some contexts, functions of the form $b^{n^k}$ for constants $b,k>1$ are considered to be exponential, even though $$ \lim_{n\to\infty}\frac{b^{n^k}}{c^n}=\lim_{n\to\infty}b^{n^k-n\log_b c}=\infty\,.$$ For example, the complexity class EXP is defined as the class of languages decided by Turing machines running in time $O(2^{n^k})$ for any $k$. Thanks to Yuval Filmus for pointing this out.

$\endgroup$
  • $\begingroup$ Can you provide some references? If there is no significant reference or usage, then it is rather void of practical importance to define a term just for the sake of that term, even though there might be a natural meaning for it. It might be better to leave its definition for better occasions. $\endgroup$ – Apass.Jack Nov 12 '18 at 13:35
  • $\begingroup$ References for which part? "Super-exponential" follows, e.g., "super-polynomial"; "sub-exponential" follows, e.g., "sub-linear", and the definition of EXP is in any complexity theory textbook. $\endgroup$ – David Richerby Nov 12 '18 at 13:47
  • $\begingroup$ References to existing articles, textbook, papers that define and use "super-exponential", the term in the question. In fact, let me ask the OP. $\endgroup$ – Apass.Jack Nov 12 '18 at 13:59
3
$\begingroup$

Using David's definition; a function is super-exponential if it grows faster than any exponential function. More formally, this means that it is $\omega(c^n)$ for every constant $c$, i.e., if $\lim_{n\to\infty} f(n)/c(n)=\infty$ for all constants $c$.


The $n$-th formula of Catalan Numbers is given by Wikipedia as;

$$ C_n \approx \frac{4^n}{n^{3/2}\sqrt \pi} $$

Than we have;

$$4^n > \frac{4^n}{n^{3/2}\sqrt \pi} > 2^n$$


By the definition of super-exponential time, $4^n$ not super-exponential time, this implies $C_n$ also not super-exponential time. Since we have;

$$\lim_{n \rightarrow \infty} \frac{f(n)}{4^n} = \infty,$$ with super-exponential growing function $f$.

This implies that Catalan numbers are exponential, not super-exponential.


    1. Note: Answer updated after David's comments.
    1. Note: In, Analytic Combinatorics, Sedgewicks says that Catalan Numbers is roughly comparable to an exponential, $4^n$, modulated by a subexponential factor. here $1/\sqrt{π n^3}.$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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