Is "super-exponential" a precise definition of algorithmic complexity?
&quot;Super-exponential&quot; 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 &quot;sub-exponential&quot; if it is $o(c^n)$ for every constant $c&gt;1$, i.e., $\lim_{n\to\infty} f(n)/c^n=0$ for all constants $c&gt;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&gt;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.