1
$\begingroup$

 I found the following description when I was reading a paper on computational complexity theory.

This can be done ... in time 2n・poly(logs,n)+2O(logs)c. For s≤2no(1), the runtime is 2n・poly(n).

I know this means substituting s≤2no(1) for 2n・poly(logs,n)+2O(logs)c results in 2n・poly(n), but I don't know how this is done. So please tell me the calculation process.

$\endgroup$

1 Answer 1

1
$\begingroup$

First let us notice that $\log s = n^{o(1)} = o(n)$, and so $\mathit{poly}(\log s, n) = \mathit{poly}(n)$. This shows that the first summand is $2^n \mathit{poly}(n)$.

Next, since $\log s = n^{o(1)}$, also $O(\log s) = n^{o(1)}$ (since constants are $n^{o(1)}$) and $O(\log s)^c = n^{o(1)}$ (since a constant multiple of $o(1)$ is also $o(1)$), hence the second summand is $2^{n^{o(1)}} = o(2^n)$. So the first summand is more significant.

$\endgroup$
1
  • $\begingroup$ I'd appreciate your answer. I was able to take the first step in your answer, but I didn't know the second step. Now I clearly understand it thanks to your explicit explanation. $\endgroup$
    – NEUTRON
    Commented May 23, 2019 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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