Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By johng

Math Help - show that n! is not O(2^n)?

  1. #1
    Newbie
    Joined
    Aug 2013
    From
    pakistan
    Posts
    22

    show that n! is not O(2^n)?

    solution:
    please check if i do it write or wrong
    n!=n*(n-1)*(n-2)...*3*2*1
    let n=4 so we have
    n!=n*(n-1)*(n-2)*(n-3)
    = (n^2 - n)(n-2)(n-3)
    =(n^3 -2n^2 - n^2 + 2n)(n-3)
    =(n^3 -3n^2+2n)(n-3)
    =n^4 - 3n - 3n^3 -3n^2 +2n^2 -6n
    n!=n^4 -3n^3 - n^2 - 9n
    so its big O is
    O(n!)=O(n^4 -3n^3 - n^2 - 9n)
    =O(n^4)
    putting n=4 , we have
    O(n!)=O(n^n)

    which proves that n! is not O(2^n)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Aug 2013
    From
    pakistan
    Posts
    22

    Re: show that n! is not O(2^n)?

    any reply please
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    635
    Thanks
    257

    Re: show that n! is not O(2^n)?

    Hi Annie,
    I'm afraid I must say your attempt is just not right. See the attachment for a proof.

    show that n! is not O(2^n)?-mhfdiscretemath4.png
    Thanks from annie12
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Show (4n^2 + 4n + 1)^m is odd
    Posted in the Calculus Forum
    Replies: 5
    Last Post: November 5th 2009, 01:01 PM
  2. Show there is exactly one y e R...
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 4th 2009, 01:27 AM
  3. How to show
    Posted in the Geometry Forum
    Replies: 4
    Last Post: August 9th 2009, 01:45 PM
  4. Show That...
    Posted in the Differential Equations Forum
    Replies: 4
    Last Post: August 9th 2009, 12:38 PM
  5. how to show show this proof using MAX
    Posted in the Calculus Forum
    Replies: 2
    Last Post: January 14th 2009, 12:05 PM

Search Tags


/mathhelpforum @mathhelpforum