Computer Science Computer Science Forum

 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? March 6th, 2014, 05:44 AM #2 Global Moderator   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)!. Tags big, proving Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post rain Abstract Algebra 4 May 11th, 2013 10:15 AM suomik1988 Linear Algebra 1 April 29th, 2011 09:57 PM isuki Elementary Math 5 July 27th, 2009 11:55 PM ^e^ Real Analysis 6 March 1st, 2007 08:16 PM isuki Number Theory 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      