CODEWITHSUNDEEP
algorithmsortingmathbig-o
StrugglingStudent202
StrugglingStudent202

Reputation: 65

Show 2^n is O(n!)

I am struggling to understand why they are equal. Help would be appreciated. I have tried saying how 2^n implies doubling n times but I am not sure how that is similar to a factorial.

Upvotes: 0

Views: 8103

Answers (2)

Peter Cheng
Peter Cheng

Reputation: 758

2^n and n! are not "equal". In formal mathematics, there is an important distinction that is often overlooked when people say "function a is O of b". It just means that asymptotically, b is an upper bound of a. This means that, technically, n is O(n!), 1 is O(n!), etc. These are trivial examples. Likewise, n! is not O(2^n).

Informally, especially in computer science, the big O notation often can be used somewhat differently to describe an asymptotic tight bound where using big Theta Θ notation might be more factually appropriate in a given context.

wikipedia

Upvotes: 0

trincot
trincot

Reputation: 350290

To prove that 2n is O(n!), you need to show that 2n ≤ M·n!, for some constant M and all values of n ≥ C, where C is also some constant.

So let's choose M = 2 and C = 1.

For n = C, we see that 2n = 2 and M·n! = 2, so indeed in that base case the 2n ≤ M·n! is true.

Assuming it holds true for some n (≥ C), does it also hold for n+1? Yes, because if 2n ≤ M·n! then also 2n+1 ≤ M·(n+1)!

The left side gets multiplied with 2, while the right side gets multiplied with at least 2.

So this proves by induction that 2n ≤ M·n! for all n ≥ C, for the chosen values for M and C. By consequence 2n is O(n!).

Upvotes: 2

Related Questions