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

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?

CodePudding user response：

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

CodePudding user response：

You can try working with Stirling's approximation for n! https://en.wikipedia.org/wiki/Stirling's_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

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

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