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.

  • $\begingroup$ my mistake lol $ $ $\endgroup$ – Ethan Jul 21 '13 at 0:42
  • $\begingroup$ 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 $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Adriano Jul 21 '13 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.