My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
March 6th, 2014, 03:34 AM   #1
Newbie
 
Joined: Jun 2012

Posts: 9
Thanks: 0

proving big O

so, I have a question that is stated: prove 2^n=O(n!)

here is my attempt to prove that the statement is true or false:

2^1=2 1!=1 false 2 is not <= 1
2^2=4 2!=2 false 4 is not <=2
2^3=8 3!=6 false 8 is not <= 6
2^4=16 4!=24 true 16<=24
2^5=32 5!=120

it looks like the statement is true only when n is greater then or equal to 4. am I following this correctly?
nealelliott is offline  
 
March 6th, 2014, 05:44 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: proving big O

"It looks like" isn't going to help here, since you're asked to prove the inclusion.

Here's a thought. Suppose 2^n < n! for some n > 1. Then 2^(n+1) = 2^n * 2 < n! * 2 < n! * (n+1) = (n+1)!.
CRGreathouse is offline  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
big, proving



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Need help with proving rain Abstract Algebra 4 May 11th, 2013 10:15 AM
Proving something is a subspace by proving it is a span. suomik1988 Linear Algebra 1 April 29th, 2011 09:57 PM
Proving... Help me plz... isuki Elementary Math 5 July 27th, 2009 11:55 PM
proving log(a) ^e^ Real Analysis 6 March 1st, 2007 08:16 PM
Proving... Help me plz... isuki Number Theory 0 December 31st, 1969 04:00 PM





Copyright © 2018 My Math Forum. All rights reserved.