1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of Sorting functions by asymptotic growth $\endgroup$ – David Richerby Jan 24 '17 at 0:13
  • 1
    $\begingroup$ Take the logarithm on both sides. $\endgroup$ – gnasher729 Jan 24 '17 at 0:19
  • 1
    $\begingroup$ @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. $\endgroup$ – Rick Decker Jan 24 '17 at 1:17
  • $\begingroup$ 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$. $\endgroup$ – jbapple Jan 24 '17 at 2:51
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Jan 24 '17 at 11:26
3
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ That makes sense to me, I understand that approach. I guess my concern was that I needed to prove it using the formal definition only rather than a limit. $\endgroup$ – FinalVersus Jan 24 '17 at 17:05
  • 1
    $\begingroup$ The limit approach implies the formal definition. $\endgroup$ – Yuval Filmus Jan 24 '17 at 17:06
  • $\begingroup$ Ohh, alright I believe I see how that works now. Thank you. $\endgroup$ – FinalVersus Jan 24 '17 at 17:08
  • $\begingroup$ how did you derive k/ln(c)? $\endgroup$ – FinalVersus Jan 25 '17 at 2:19
  • $\begingroup$ The derivative of $n^k$ (with respect to $n$) is $kn^{k-1}$, and that of $c^n$ is $c^n\ln c$. $\endgroup$ – Yuval Filmus Jan 25 '17 at 7:43

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.