# Substitution for Landau's O notation formula

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.

## 1 Answer

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.

• 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. Commented May 23, 2019 at 7:32