Is $O(n^k \log n)$ of smaller time complexity than $O(n^{k+\epsilon})$?

Question

Is it true that asymptotically, $O(n^k \log n)$ is of smaller time complexity than $O(n^{k+\epsilon})$ for $\epsilon>0$? How might I prove this one way or the other?

Answer 1

This is true. This is equivalent to saying that, for every $\epsilon>0$, $\log(n)$ is asymptotically smaller than $n^\epsilon$. To see that this is the case, take a derivative of the functions to get $x^{-1}$ and $x^{-(1-\epsilon)}$. Since the second is larger for every $x>1$, $n^\epsilon$ grows faster at every point than $\log(n)$ and so will eventually be larger. Once it gets larger, it stays larger.