Using the definition of big-oh notation, show that for any $k,\gamma>1$, $n^k=O(\gamma^n)$.

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.

• my mistake lol  – Ethan Jul 21 '13 at 0:42
• If $n>\frac{-kW(-\frac{\ln(a)}{k})}{\ln(a)}$ then $n^k<a^n$, for all real $a,k$. Where W denotes the lambert W function – Ethan Jul 21 '13 at 1:03

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$.
• So putting everything together, let $C=\dfrac{1}{(\gamma^{1/k}-1)^k}$ and $n_0=1$. Then for all $n\ge 1$, we have: \begin{align*} n^k &= \dfrac{1}{(\gamma^{1/k}-1)^k}((\gamma^{1/k}-1)n)^k \\ &= C((\gamma^{1/k}-1)n)^k \\ &< C(1+(\gamma^{1/k}-1)n)^k \\ &\le C((1+\gamma^{1/k}-1)^n)^k & \text{by Bernoulli's Inequality}\\ &= C(\gamma^{1/k})^{kn} \\ &= C\gamma^n \\ \end{align*} Awesome. – Adriano Jul 21 '13 at 23:02