How to prove an polynomial run time is faster than exponential using definition of big O
In order to prove that $f(n) = o(g(n))$ (and so $f(n) = O(g(n))$) for two positive functions $f(n),g(n)$, it is enough to prove that
$$
\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0.
$$
In your case, you can use L'Hôpital's rule, together with induction on $k$. We will show that for all integer $k \geq 0$ and all $c &gt; 1$,
$$
\lim_{n\to\infty} \frac{n^k}{c^n} = 0.
$$
This is clear for $k = 0$. Given that it holds for $k-1$, it holds for $k$ since
$$
\lim_{n\to\infty} \frac{n^k}{c^n} = 
\lim_{n\to\infty} \frac{k}{\ln c} \frac{n^{k-1}}{c^n} = 0,
$$
by the induction hypothesis.

If $k$ is not integral, the result still holds, since $n^k \leq n^{\lceil k \rceil}$.