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?
How to prove an polynomial run time is faster than exponential using definition of big O
asymptotics;runtime analysis;polynomial time
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'Hpital'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}$.