CODEWITHSUNDEEP
mathtime-complexity
Integrity
Integrity

Reputation: 23

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

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?

Upvotes: 1

Views: 123

Answers (2)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186813

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^)

Upvotes: 1

jdkramhoft
jdkramhoft

Reputation: 368

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

Upvotes: 2

Related Questions