2
$\begingroup$

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.

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

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

Since the term "sub-exponential" is loaded, it is better to mention what you mean by it whenever you use it.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Matt Groff Feb 6 '14 at 21:27
  • 1
    $\begingroup$ @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)}$". $\endgroup$ – Luke Mathieson Feb 6 '14 at 21:43
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 6 '14 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.