# Which of $e^n$ and $2n^2$ grows faster? [duplicate]

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

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

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$.
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)$.
• 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$. Commented Feb 4, 2014 at 1:20
• 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 Commented Feb 4, 2014 at 8:35