October 3rd, 2012, 05:29 PM  #1 
Newbie Joined: Oct 2012 Posts: 2 Thanks: 0  BigO notation estimates
All, Im having some trouble understanding BigO estimates. Im using Discrete Mathematics And Its Applications by Rosen 6th Edition. In section 3.2 one of the example problems says to show that f(x)  x^2 + 2x + 1 is O(x^2). The solution states the following: ++++++++++++++ "We observe that we can readily estimate the size of f(x) when x > 1 because x < x^2 and 1 < x^2 when x > 1. It follows that 0 <= x^2 + 2x + 1 <= x^2 + 2x^2 + x^2 = 4x^2 whenever x > 1. ... Consequently, we can take C = 4, k = 1 as witnesses to show that f(x) is O(x^2). That is, f(x) = x^2 + 2x + 1 = 4x^2 whenever x > 1. ++++++++++++++ I have read this so many times and for some reason the concept is not sticking. Im hoping someone can explain how this problem was worked. Here is what I dont understand: Why is "0<=" being used here? How did we go from x^2 + 2x + 1 to x^2 + 2x^2 + x^2? I thought maybe we are using the value of g of x (x^2) to replace the x values in the f(x) function but should this not be x^4 + 2x^2 + 1? Any help would be appreciated. 
October 4th, 2012, 05:47 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: BigO notation estimates
I'm just going to 'start over' with f(x) = x^2 + 2x + 1, not trying to figure out what the book might have meant precisely. Once you understand this you'll probably be able to look back at the book and figure out what was meant there (or if there was a typo, etc.). So saying that something is O(x^2) means that it grows no faster than some fixed multiple of x^2 as x gets big. (Actually it could be used as x limits toward any value, but +infinity is the most common by far in this application.) Sometimes instead of writing f(x) = O(x^2) you'll see f(x) << x^2 which means the same thing. This has the advantage of not looking like an equality, which it really isn't (though you can interpret it as an existential equality if you like...). So x = O(x^2) since for x > 1 you have x < 1 * x^2. Similarly, 1 = O(x^2) for the same reason. So you have f(x) = x^2 + 2x + 1 <= x^2 + 2x^2 + 1 <= x^2 + 2x^2 + x^2 = 4x^2 for x >= 1. So this is exactly what you wanted: f(x) is at most some fixed multiple of x^2 as x gets large (in this case, "large" means at least 1). So this is written f(x) = O(x^2) or f(x) << x^2. 
October 4th, 2012, 08:24 AM  #3 
Newbie Joined: Oct 2012 Posts: 2 Thanks: 0  Re: BigO notation estimates
Thanks so much for the reply. I think I am starting to understand here. I still don't understand how the author came up with 4x^2. f(x) = x^2 + 2x + 1 <= x^2 + 2x^2 + 1 <= x^2 + 2x^2 + x^2 = 4x^2 So here is an example of one of the problems at the end of the section. Determine whether each of these functions is O(x^2): f(x) = 17x + 11 Using what I have learned to solve this I will need to determine 2 witnesses(k, C). k value must be chose to find the value of C for which f(x)<=Cg(x^2). k should be less than x and x^2 should be larger than x which means that x must be larger than 1 (x >1). I know that I must begin to write out the equation to test the result. 0<= 17x + 11 ? (some new equation based on k goes here?) This is the part that does not make sense to me. I know the answer to this question but I dont know the mechanics of how it happened. The answer is this: 17x + 11 ? 17x + x = 18x ? 18x2 when x > 11. Here, C = 18 and k = 11. Why did the 11 go away here 17x + x Is there some rule that we must make all numbers a multiple of x in the equation? I am guess x was placed because of 17x. In the first problem I posted I asked, How did we go from x^2 + 2x + 1 to x^2 + 2x^2 + x^2? Maybe this is because we must replace or make all none multiples of x to be a value of x. Since the lowest value of exponent of x was x^2 then any other exponent of x must be x^2 and any other none multiple of x must become simply x^2. This is all my assumption, but was hoping maybe someone could clear this piece up for me. Here is another part of the same question: Determine whether each of these functions is O(x^2): f(x) = x^2 + 1000 Using my shotty logic above I would work the problem as follows: x^2 + 1000 <= x^2 + x^2 <= 2x^2 Here we show that C = 2 and k = 1000. This function is O(x^2) because the answer 2x^2 is a valid multiple of x^2. Am I getting close? 
October 4th, 2012, 09:46 AM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: BigO notation estimates Quote:
It almost feels silly to write "11 <= x for all large x"  you're taking the limit as x increases without bound, so you can assume it's larger than a million, or a billion, if you need.  

Tags 
bigo, estimates, notation 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Who defines statistics as the science of estimates and proba  xy8797  Probability and Statistics  1  December 20th, 2012 08:03 PM 
Upper and Lower Estimates Problem  jskrzy  Algebra  3  October 23rd, 2012 07:06 PM 
Derivative Estimates  phoebe  Complex Analysis  0  November 2nd, 2011 07:45 PM 
Statistics: Two designs to obtain estimates  bluesilver  Advanced Statistics  1  December 11th, 2006 02:08 PM 
Upper and Lower Estimates Problem  jskrzy  Calculus  3  December 31st, 1969 04:00 PM 