3
$\begingroup$

How would you prove/disprove that $e^n = O(2n^2)$? It's unclear to me which function grows faster.

$\endgroup$
1
  • $\begingroup$ Rule of thumb: $(\log n)^a < n^c < b^n$ for sufficiently large $n$ for all $a,c > 0$ and $b > 1$. $\endgroup$
    – G. Bach
    Feb 4, 2014 at 1:19

2 Answers 2

4
$\begingroup$

Try plotting them. You can also notice that as $n$ increases by one, $e^n$ increases by a multiplicative factor of $e^{n+1}/e^n=e$, while $2n^2$ increases by a multiplicative factor of $\frac{2(n+1)^2}{2n^2} \longrightarrow 1$.

$\endgroup$
2
$\begingroup$

You can avoid $O(2n^2)$ by $O(n^2)$. On the other hand, you have:

$$ \lim_{n\to\infty} \frac{n^2}{e^n} = \lim_{n\to\infty} \frac{2n}{e^n} = \lim_{n\to\infty} \frac{2}{e^n} = 0 $$ So, $\lim_{n\to\infty} \frac{n^2}{e^n} = 0$ say us that $O(n^2) \subset O(e^n)$. Therefore, $O(2n^2) = O(n^2) \subset O(e^n)$.

$\endgroup$
3
  • $\begingroup$ This is actually the way to go probably since if you don't use a limit rule, you'll have to fiddle around with the series expansion of $e^n$. $\endgroup$
    – G. Bach
    Feb 4, 2014 at 1:20
  • 5
    $\begingroup$ I think you have an error in your calculation: I assume you used L'Hospital's rule, but $\frac{d}{dn}e^{n} = e^{n}$. Hence $\lim\limits_{n \rightarrow \infty}\frac{n^2}{e^n} = \lim\limits_{n \rightarrow \infty} \frac{2n}{e^n} = 2 \lim\limits_{n \rightarrow \infty} \frac{1}{e^n} = 0$, by applying L'Hospital's rule twice $\endgroup$
    – Gaste
    Feb 4, 2014 at 8:35
  • $\begingroup$ @Gaste you're right, I posted it so fast and I forgot to review it. thanks. $\endgroup$ Feb 12, 2014 at 4:28

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