# Is there a designation for this not-quite-exponential time?

I've been working and experimenting with an algorithm that may take time $O^*(2^\sqrt{n})$. Here $O^*(f(n))$ simply neglects all polynomial terms. I've seen a comment on Scott Aaronson's blog that mentions graph isomorphism algorithms run in this time, too. Actually, $O(2^\sqrt{n})$. Is there a designation for this time?

I thought perhaps quasi-exponential may describe it, but I'm wondering if there is already a name/designation for it.

• It's subexponential (and superpolynomial, if it's also in $\Omega$ of something similar). – Raphael Feb 6 '14 at 21:14

Two useful classes are sub-exponential, $c^{n^\epsilon}$ for $\epsilon \in (0,1)$, and quasi-polynomial, $c^{\log^k n}$ for $k > 1$. (In both cases, $c > 1$.)
The terms themselves sometimes have different meanings. For example, in some contexts "sub-exponential" means $2^{(1-\epsilon)n}$ for some $\epsilon > 0$, and in others it means $2^{o(n)}$.
• According to Wikipedia, being sub-exponential requires the time to be valid for all $\epsilon \in (0,1)$. So it seems that this wouldn't qualify for sub-exponential, correct? – Matt Groff Feb 6 '14 at 21:27
• @MattGroff, Subexponential is an overloaded term; see the first line of the second definition on Wikipedia,"Some authors define sub-exponential time as running times in $2^{o(n)}$". – Luke Mathieson Feb 6 '14 at 21:43
• The three definitions in common use for subexponential are $c^{n^\epsilon}$, $2^{(1-\epsilon)n}$, and the one Luke quoted (e.g. is $2^{n/\log n}$ sub-exponential?). When in doubt, mention both the term and the meaning you give to it. – Yuval Filmus Feb 6 '14 at 22:34