Is "super-exponential" a precise definition of algorithmic complexity?

Question

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

Answer 1

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

Answer 2

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