My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
October 3rd, 2012, 06: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.
JoeD is offline  
 
October 4th, 2012, 06:47 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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.
CRGreathouse is offline  
October 4th, 2012, 09: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?
JoeD is offline  
October 4th, 2012, 10:46 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
bigo, estimates, notation



Search tags for this page
Click on a term to search for related topics.
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 09:03 PM
Upper and Lower Estimates Problem jskrzy Algebra 3 October 23rd, 2012 08:06 PM
Derivative Estimates phoebe Complex Analysis 0 November 2nd, 2011 08:45 PM
Statistics: Two designs to obtain estimates bluesilver Advanced Statistics 1 December 11th, 2006 03:08 PM
Upper and Lower Estimates Problem jskrzy Calculus 3 December 31st, 1969 04:00 PM





Copyright © 2017 My Math Forum. All rights reserved.