# 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? Commented Nov 12, 2018 at 14:03
• Here is a definition of super-exponential growth: services.math.duke.edu/education/postcalc/growth/growth4_1.html Commented Aug 19, 2020 at 16:46

"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=0$$ 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. Commented Nov 12, 2018 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. Commented Nov 12, 2018 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. Commented Nov 12, 2018 at 13:59
• There are also claims that superexponential has to be nonelementary. I have compiled three levels of superexponential growth. Commented Jan 14 at 3:24

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

The term 'superexponential' is not a precise description of algorithmic complexity, but it always suggests a growth greater in order than a simple exponential function of form $$b^n$$ for some $$b > 1$$. There are three main levels of superexponential growth:

1. Beyond the class E, the class of all problems with simple exponential complexity. A problem in E has complexity upper-bounded by an expression of the form $$b^n$$ where $$b > 1$$.
• Two exponential functions with different bases are of different orders of growth. Namely, $$2^n$$ is little-o of $$e^n$$, which in turn is little-o of $$10^n$$. Using the properties of change of bases, simple exponential time is $$2^{O(n)}$$ time.
• Factorial $$n!$$ time is superexponential under the first definition, but not in the latter two. It is often categorized separately from exponential algorithms. Also, $$(n + 1)!$$ is of different orders of growth than $$n!$$.
• The asymptotic formula for Catalan numbers would fall under this category. Even if the function is not of a simple exponential form, it is still upper bounded by a simple exponential function $$4^n = 2^{2n}$$.
2. Beyond the class EXPTIME, the full exponential complexity class. The complexity of a problem in EXPTIME is upper-bounded by an expression of the form $$b^{g(n)}$$ where $$b > 1$$ and $$g(n)$$ is polynomial growth.
• Factorial growth is slower than $$n^n$$ growth. However, $$n^n$$ can be converted to an exponential expression $$e^{n \ln n}$$, and the exponent exhibits polynomial-order growth. Thus, factorial time is EXPTIME, but is still upper-bounded by an expression requiring only one font size.
• The doubly exponential expression $$2^{2^x}$$ is superexponential under the second definition as well as the first, but not the third. You need three font sizes to write down this expression or an upper bound. This function, however, does not involve any higher hyperoperators aka 'superexponentiation'.
3. Being nonelementary, meaning that the expression for the upper bound cannot be done with nested exponents at all.
• In fact, the word 'superexponent' may refer to tetration, which is used in an actual mathematics journal (Nick Bromer, 1987).
• Professor Brailsford from a Computerphile video about primitive recursion and the Ackermann function, discussed that one indication of a function that has to be done recursively is when the function starts behaving superexponentially (Computerphile, 2014, 12′45″). By superexponential, he means the third definition. It is not the growth rate of $$n^n$$ (he said "which would be exponential"), but is $$\underbrace{n^{n^{n^{\cdot^{\cdot n}}}}}_n$$.