# Do exponents have higher time complexity than factorials? [duplicate]

My professor said exponentials will always have higher time complexity compared to polynomials. My question is, do exponentials also have higher time complexity than factorials?

I plotted a chart in Matlab to check it myself.

When range of x is small, from 1 to 10, I get the following chart,

%Matlab script
x  = [1 : 10];
y1 = factorial(x);
y2 = exp(x);

plot(x', [y1',y2']);
title("N! vs e^N");
legend("O(n!)", "O(e^n)"); Here factorial is clearly beating exponential.

But when I bump the range of x from 1 to 1000, I get the following chart,

x  = [1 : 1000]; Here exponential is clearly beating factorial.

So, can I say conclusively that exponentials will always have higher time complexity than both factorials and polynomials?

-

In fact $$e^n$$ is $$o(n!)$$. We could show it using the Stirling approximation by taking limit $$\lim_{n\rightarrow \infty}{\frac{e^n}{(\sqrt{2\pi n})(\frac{n}{e})^n}} = \lim_{n\rightarrow \infty}{\frac{e^{2n}}{(\sqrt{2\pi n})n^n}} = \lim_{n\rightarrow \infty}{\frac{1}{\sqrt{2\pi n}}\frac{e^{2n}}{n^n}}$$

Since $$\lim_{n\rightarrow \infty}{\frac{1}{\sqrt{2\pi n}}} = 0$$ we only need to calculate $$\lim_{n\rightarrow \infty}{\left(\frac{e^2}{n}\right)^n}$$ The function $$\frac{e^2}{n}$$ decreases faster than any function $$c^n$$ where $$0 < c < 1$$ for sufficiently large $$n$$s (as $$n$$ goes to infinity), and so $$\lim_{n\rightarrow \infty}{\left(\frac{e^2}{n}\right)^n} = 0$$.

I am not a Matlab user, but these are plots for $$e^x$$ and Stirling approximations of $$n!$$ using Wolfram script: plot (1\sqrt(2*pi*x)*(x/e)^x) from 0 to 6, plot(e^x) from 0 to 6 As you see $$n!$$ overtakes $$e^n$$ when $$n=6$$.
• @fade2black"I want to show at what point one function overtakes other one." > This is correct. Our professor is asking us to plot 2 graphs for each pair of functions. One to show the crossing points, and another to show that for sufficiently large X one function clearly dwarfs another. I was having trouble plotting both of the graphs. – Quazi Irfan Sep 24 '17 at 19:36
• @QuaziIrfan then plot $\frac{e^n}{n!}$ and see, it should go to zero as $n$ goes to infinity. – fade2black Sep 24 '17 at 19:42