0

I am reading about big O notation on wikipedia, and it say the following;

For any $k>0$ and $c>0$, $O(n^{c}(\log n)^{k})$ is a subset of $ O(n^{c+\epsilon })$ for any $\epsilon >0$, so may be considered as a polynomial with some bigger order.

I am struggling to see this. In particular, I can not see how this would hold for every $\epsilon>0$. It is clear that it holds for $\epsilon\geq k$, but how would it be shown for $0<\epsilon<k$?

Thanks

Mr Martingale
  • 912
  • 2
    It should follow from $$\lim_{n \to +\infty} \frac{(\log n)^k}{n^\varepsilon}=0.$$ – Siminore May 03 '18 at 11:08
  • The logarithm has a big impact on $n$. So if $n$ gets sufficient big, the differnce cause by $\log n$ goes to zero. There will be a point, for large enough $n$, where $n^c(\log n)^k\leq n^{c+1}$ – Patrick Abraham May 03 '18 at 11:17
  • Okay, this makes sense. If I am not mistaken, can the same argument can be used to show $O(n^c(\log{n})^{k_1}(\log\log{n})^{k_2})=O(n^{c+\epsilon})$ for any $\epsilon>0$? – Mr Martingale May 03 '18 at 12:27

0 Answers0