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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityIs 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.
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.