Which one is faster? O(2^n) or O(n!)

user_16190751 0
Viewed 45

I'm studying algorithm complexity and I am trying to figure out this one question that runs in my mind- is O(n!) faster than O(2^n) or is it the opposite way around?

math time-complexity
2 Answers

O(2^n) is 2 * 2 * 2 * ... where O(n!) is 1 * 2 * 3 * 4 * ...

O(n!) will quickly grow much larger - so O(2^n) is faster.

For example: 2^10 = 1024 and 10! = 3628800

user_160766730

You can try working with Stirling's approximation for n! https://en.wikipedia.org/wiki/Stirling%27s_approximation

 n! = (n / e)^n * sqrt(2 * Pi * n) * (1 + o(n))

Now, let's compare

 O(n!) <=> O(2^n)

In order to find out the right letter <, = or > let's compute limit

 lim (n! / 2^n) =
   n -> +inf

 lim (n / e)^n * sqrt(2 * pi * n) / 2^n >=
   n -> +inf

 lim n^n / (2 * e)^n >= // when n > 4 * e
   n -> +inf

 lim (4 * e)^n / (2 * e)^n =
   n -> +inf 

 lim 2^n = +inf
   n -> +inf

So

 lim (n! / 2^n) = +inf
   n -> +inf

which means that O(n!) > O(2^)

user_23194070
Related