# How to prove an polynomial run time is faster than exponential using definition of big O

This is for homework so feel free to not give me an answer but steer me in the right direction.

The problem states:

Prove that $n^{1000000} = O(1.000001^n)$ using the formal definition of Big-O.

The definition of Big-O is:

$\hspace{2cm}T(n)=O(f(n)):\,\exists\;c\gt0\;$ and $\;n_0\ge0,\;$ such that $\;T(n)\le c\cdot f(n)$

Now, I know that there is also the definition that

$\hspace{4cm}$For every $\;r\gt0\;$ and $\;d\gt0,\; n^d = O(r^n)$

But how exactly am I supposed to prove this without using induction or a limit equation? Any guidance on where to start?

This is what I have so far:

$\hspace{7.6cm}\frac{T(n)}{f(n)}\le c$

$\hspace{6.8cm}\frac{n^{1000000}}{1.000001^n}\le c$

$\hspace{6cm}\frac{1.000001^{1000000n}}{1.000001^n}\gt\frac{n^{1000000}}{1.000001^n}$

EDIT: I continued simplifying.

$\hspace{5.4cm}1.000001^{999999n}\gt\frac{n^{1000000}}{1.000001^n}$

Do I stop here?

$\hspace{5.3cm}1.000001^{1000000n}\gt n^{1000000}$

$\hspace{3.4cm}1000000n\cdot log(1.000001)\gt 1000000\cdot log(n)$

$\hspace{5.8cm}log(1.000001)\gt \frac{1}{n}\cdot log(n)$

$\hspace{6.8cm}1.000001\gt n^{1/n}$

What would the above even tell me?

• Possible duplicate of Sorting functions by asymptotic growth – David Richerby Jan 24 '17 at 0:13
• Take the logarithm on both sides. – gnasher729 Jan 24 '17 at 0:19
• @gnasher729. That'll work in this case, but you have to be careful when taking logs in general, lest you conclude $2^n=\Theta(3^n)$ by taking logs of both sides. – Rick Decker Jan 24 '17 at 1:17
• First, you definition of Big-O is wrong: $n_0$ is never used and $n$ is free. Second, your second definition is a proposition, not a definition. Third, this proposition is false for $r < 1$. – jbapple Jan 24 '17 at 2:51
• There is no definition which states that $n^d = O(r^n)$. This is something that follows from the definition, in other words, a theorem. Also, your definition is wrong: we only require $T(n) \leq c\cdot f(n)$ for $n \geq n_0$. – Yuval Filmus Jan 24 '17 at 11:26

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 > 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}$.
• The derivative of $n^k$ (with respect to $n$) is $kn^{k-1}$, and that of $c^n$ is $c^n\ln c$. – Yuval Filmus Jan 25 '17 at 7:43