If you want to make money online : Register now

[Solved]: Is there a designation for this not-quite-exponential time?

, , No Comments
Problem Detail: 

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.

Asked By : Matt Groff

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21397

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback