Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to prove expontential = O (n!)

  1. Oct 6, 2012 #1
    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!
     
  2. jcsd
  3. Oct 6, 2012 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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).
     
  4. Oct 6, 2012 #3
    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!
     
  5. Oct 9, 2012 #4
    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!
     
  6. Oct 9, 2012 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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:

     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook