My Math Forum

My Math Forum (http://mymathforum.com/math-forums.php)
-   Computer Science (http://mymathforum.com/computer-science/)
-   -   proving big O (http://mymathforum.com/computer-science/41902-proving-big-o.html)

nealelliott March 6th, 2014 04:34 AM

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?

CRGreathouse March 6th, 2014 06:44 AM

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)!.


All times are GMT -8. The time now is 04:04 AM.

Copyright © 2018 My Math Forum. All rights reserved.