# Is “super-exponential” a precise definition of algorithmic complexity?

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$$?

• 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? – Apass.Jack Nov 12 '18 at 14:03

"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.

• 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. – Apass.Jack Nov 12 '18 at 13:35
• 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. – David Richerby Nov 12 '18 at 13:47
• References to existing articles, textbook, papers that define and use "super-exponential", the term in the question. In fact, let me ask the OP. – Apass.Jack Nov 12 '18 at 13:59

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: 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}.$$