My Math Forum Big-O notation estimates

 Applied Math Applied Math Forum

 October 3rd, 2012, 05:29 PM #1 Newbie   Joined: Oct 2012 Posts: 2 Thanks: 0 Big-O notation estimates All, Im having some trouble understanding Big-O 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: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Big-O 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: Big-O 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)|<=C|g(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: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Big-O notation estimates

Quote:
 Originally Posted by JoeD 17x + 11 ? 17x + x = 18x ? 18x2 when x > 11. Here, C = 18 and k = 11. Why did the 11 go away here 17x + x
11 <= x for all large x, so 17x + 11 <= 17x + x for all large x by adding 17x to both sides.

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

,
,
,
,
,

,

,

,

,

,

,

,

,

,

# determine whether the function is o(x^2) f(x)=17x 11

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post xy8797 Probability and Statistics 1 December 20th, 2012 08:03 PM jskrzy Algebra 3 October 23rd, 2012 07:06 PM phoebe Complex Analysis 0 November 2nd, 2011 07:45 PM bluesilver Advanced Statistics 1 December 11th, 2006 02:08 PM jskrzy Calculus 3 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top