How to prove expontential = O (n)

[Physicsnuubie]

Hi experts,

I came across a question to determine whether 2^n = O(n!) is true or false. If its true, i need to prove it.

I am aware of the list of growing order functions. So i suppose the statement is true.

However, I can't prove it.
anyone can help me with this? thank you very much!

 

[mfb]

Can you show that n! > 2^n for all n above some specific value?
This is easy, once you found the starting point (just calculate the first few values and you will see it).

 

[Physicsnuubie]

Hi!
Thanks for replying.

I couldn't establish the link between factorial and expontential.

2^n < kn! = kn(n-1)(n-2)...1 for n>n0

this would be the definition of big O. but how can i prove it? what values of k and n0 do i have to take?? thank you very much!

 

[Jocko Homo]

I couldn't establish the link between factorial and expontential.

2^n < kn! = kn(n-1)(n-2)...1 for n>n0

this would be the definition of big O. but how can i prove it? what values of k and n0 do i have to take?? thank you very much!

It looks like you're on the right track.

I don't want to answer your question for you but I'll lay some pretty big hints since being stuck doesn't really help you...

k and n0 don't take on any specific values. You just have to show that for any k, there exists an n0 such that your inequality will be true. As to how to show this, just take a look at your inequality. Maybe examining some concrete values will help you see a pattern:

n = 1 => 2^n = 2 > 1 = n!
n = 2 => 2^n = 2 * 2 > 2 * 1 = n!
n = 3 => 2^n = 2 * 2 * 2 > 3 * 2 * 1 = n!
n = 4 => 2^n = 2 * 2 * 2 * 2 < 4 * 3 * 2 * 1 = n!

As you can see, 2^n > n! until n >= 4. Do you think there exists an n > 4 such that 2^n > n! again? Why or why not?

If you can answer this, all you have to do in incorporate the constant k in your argument and you will have proven your claim...

Good luck!

 

[mfb]

You just have to show that for any k, there exists an n0 such that your inequality will be true.

Even better: It is sufficient to find some specific k.
k=1 works here, and you can prove it. That was the hint in my post:

Can you show that n! > 2^n for all n above some specific value?