# What is the meaning of 'moderately exponential' running time?

I was reading some research paper where for hypergraph of bounded rank $k$ they have given moderately exponential algorithm. The runtime of the algorithm is $e^{ \mathcal {O}(k^2\sqrt n) \cdot poly(n)}$. Here $k$ is the rank of the hypergraph, and $poly(n)$ means polynomial in variable $n$.

What is the meaning of moderately exponential running time ?

I have seen this link, but did not understand much.

• It's not a precisely defined term and depends on context. Aug 26, 2017 at 8:00
• So, moderately exponential according to the link means more than any polynomial, but less than any exponential. The runtime you mention does not fall in that definition, since the $Poly(n)$ in the exponent is too large. Perhaps "moderate" is only used informally, instead?
– chi
Aug 26, 2017 at 9:13
• @ adrianN In the context of isomorphism of algebraic and combinatorial structures.
– user35837
Aug 26, 2017 at 10:00
• @chi: If that is the runtime, then "moderately" is most likely meant as a joke. "We have this algorithm, but its runtime is so awful, you have no chance for any but the smallest n". Aug 26, 2017 at 19:37

From context, it seems that the meaning here is $\exp O(n^\alpha)$ for $\alpha < 1$; an exponential running time would be $\exp O(n)$ or worse.
For example, the naive exponential-time algorithm for finding a maximum independent set in a graph tries all possibilities and runs in $O^*(2^n)$ time. Thus, any (exponential-time) algorithm that runs in $O^*(c^n)$ time for any $c < 2$ can be said to be moderately exponential.