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
$\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$
  • $\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 May 23 at 7:32

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.