How would you prove/disprove that $e^n = O(2n^2)$? It's unclear to me which function grows faster.
$\begingroup$
$\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. BachCommented Feb 4, 2014 at 1:19
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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$.
answered Feb 4, 2014 at 0:34
$\begingroup$
$\endgroup$
3
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)$.
answered Feb 4, 2014 at 1:01
-
$\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. BachCommented 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$– GasteCommented Feb 4, 2014 at 8:35
-
$\begingroup$ @Gaste you're right, I posted it so fast and I forgot to review it. thanks. $\endgroup$ Commented Feb 12, 2014 at 4:28