This question had been on my midterm in a course I took last year:
Prove that for any $k,\gamma>1$, $n^k=O(\gamma^n)$.
Intuitively, this makes sense. Even the fastest exponential algorithm (for example, $1.001^n$) will eventually take a longer time to finish than the slowest polynomial algorithms (for example, $n^{999}$). Apparently, the easiest way to do this question is to show that: $$ \lim_{n\to\infty}\dfrac{n^k}{\gamma^n}=0 $$ by applying L'Hopital's Rule $\lceil k \rceil$ times. However, I want to try to prove this using the definition of big-oh notation. That is, I want to explicitly come up with some constants $C,n_0$ such that:
For all $n \ge n_0$, $0 \le n^k \le C\gamma^n$.
I've tried some small examples, hoping that the process would generalize (for example, I can show that $n^3<2^n$ for any integer $n\ge10$ using induction, although I don't know how to prove this for all real numbers). I've tried to prove the easier problem of showing that $n^k \le k^n$ for large enough $n$ by using induction and the binomial theorem, but that was a mess. I've tried working backwards and taking logs of both sides, with no luck.
I'd appreciate your thoughts. Apologies if this is a duplicate; this is likely not the first time this question has been asked.
We show that there is a constant $C$ such that if $n\ge 1$ then $n^k \lt C\gamma^k$.
A preliminary simplification is useful. It is enough to show that there is a constant $D$ such that if $n\ge 1$, then $n\lt D(\gamma^{1/k})^n$. Note that $\gamma^{1/k}\gt 1$. Call it $1+\delta$.
By the Bernoulli Inequality we have $(1+\delta)^n \ge 1+\delta n$. Thus if we take $D=1/\delta$ and $n\ge 1$, then $n^k\lt D^k\gamma^n$.