0
$\begingroup$

Is next time complexity sub-exponential?

$O(2^{N^{LOG2(1.5)}}/8)$

unformatted: O((2^N)^LOG2(1.5))/8) just in case I didn't format it properly.

$\endgroup$

marked as duplicate by Raphael Oct 25 '17 at 9:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ "next" in what sense? $\endgroup$ – Raphael Oct 25 '17 at 9:48
0
$\begingroup$

It depends on how you define subexponential. The definition I generally use is:

$$\textsf{SUBEXP} = \bigcap_{\varepsilon > 0}\textsf{DTIME}(2^{n^\varepsilon})$$

However some authors define:

$$\textsf{SUBEXP} = \textsf{DTIME}(2^{o(n)})$$

Since your function is $2^{n^c}$ for some constant $c<1$, it would be subexponential according to the second but not to the first.

$\endgroup$
  • $\begingroup$ First definition can be rewritten as $\mathsf{DTIME}(2^{n^{\ o(1)}}\ \ )$, right? $\endgroup$ – rus9384 Oct 25 '17 at 10:56

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