Showing $(\log n)^k = O(n)$, where $k\in\mathbb{N}$

Question

I'm somewhat convinced by taking the limits of $\frac{n}{(\log{n})^k}$ (i.e. proving little $o$ to prove big $O$), but am struggling to prove that it is the case via the formal definition; say the following:

We say that a function $f(n)$ is $O(g(n))$ if there exists a positive real number $M$ and a real number $x_0$ such that $$|f(x)|\leq M\cdot g(x)\quad {\text{ for all }x\geq x_{0}.}$$

I think it boils down to showing $(\log{n})^k \geq M\cdot n$, but I'm stumped.

Answer 1

For any $k\in\mathbb{N}$ and $x>k+1$ we have that $x^k<k!\frac{x^{k+1}}{(k+1)!}<k!e^x$. Take $x=\log n$ and you get that $(\log n)^k=O(n)$. [Note that $k!$ is a constant.]

Answer 2

We have $x< e^x$. Set $x = \log(n^{1/k})$. We get $$\log(n^{1/k})<n^{1/k}$$ or, equivalently $$(\log n)^k < k^k n$$