1
$\begingroup$

This question already has an answer here:

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)");

enter image description here 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]; 

enter image description here

Here exponential is clearly beating factorial.

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

-

$\endgroup$

marked as duplicate by Raphael Sep 23 '17 at 11:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

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

Regarding Quazi Irfan's comments about Matlab graph
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 enter image description here

As you see $n!$ overtakes $e^n$ when $n=6$.

$\endgroup$
  • $\begingroup$ @fade2black So my deduction is wrong. The growth of factorial function would be greater than exponentials? - Did I interpret your answer correctly? $\endgroup$ – Quazi Irfan Sep 23 '17 at 17:45
  • 1
    $\begingroup$ @QuaziIrfan n factorial eventualy grows faster than exp(n). In fact it is true for any constant base. $\endgroup$ – fade2black Sep 23 '17 at 17:52
  • 2
    $\begingroup$ That plot is useless; see e.g. here. If you want to use plots to drive your work, plot the quotient and check whether it seems to converge. Log(-log) plots can also be useful when large functions are involved. $\endgroup$ – Raphael Sep 24 '17 at 13:11
  • 1
    $\begingroup$ @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. $\endgroup$ – Quazi Irfan Sep 24 '17 at 19:36
  • 2
    $\begingroup$ @QuaziIrfan then plot $\frac{e^n}{n!}$ and see, it should go to zero as $n$ goes to infinity. $\endgroup$ – fade2black Sep 24 '17 at 19:42

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