Results 1 to 9 of 9

Math Help - Big Oh Notation

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    3

    Big Oh Notation

    Hi guys,
    I was wondering if someone could explain to me how Big Oh notation works in plain english. after reading many articles, watching videos and reading text book chapter over and over, i am still not 100% clear. First of all, let me tell you what I understand so far:
    Big Oh notation gives you the upper bound of a function. I understand that f(x) is O(g(x)) if there are constants C and k such that f(x) is less than or equal to C.g(x) whenever x > k

    I guess my main problem is I am not sure how people actually come up with the 2 constants.It seems like everyone has their own way of solving it. Can someone please give me the easiest way to remember how to come up with the 2 witnesses.

    For example: Show that f(x) = x^2+2x+1 is O(x^2)

    one of the tutorials i was looking at suggested we only pay attention to the highest term. in this case x^2. and since x^2 has a coeffiecient of 1, that becomes one of the constant C. we then get k by adding all the terms of f(x) and pretending they all have x^2. i.e x^2+2x^2+1x^2 = 4x^2. Then we get 4 as the other constant and we have C = 1, k = 4.

    however, in my textbook they have the following solution:

    Solution: 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.

    I get lost at the very first part where it says we can readily estimate the size of f(x) when x > 1 because x < x^2..... where are they getting x from?


    i feel like i have some kind of mental block because i understand the concept but not sure HOW to go about showing it..

    any help would be really appreciated!! sorry for a loooong posting.. thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Mar 2009
    Posts
    378
    O(h) essentially means that the quantity goes to zero at the same rate as h. Or that the quantity is similar in magnitude as h.

    The x<x^2 is coming from the 2x in f(x). Here they are saying that when x>1 we know that x^2>x and therefore 2x^2 > 2x. You can then apply this reasoning to the constant in f(x), i.e. when x>1 x^2>1. Putting all this together we have that x^2+2x+1 < x^2 +2x^2 +x^2 = 4x^2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2010
    Posts
    86
    The most simple way to explain it is an example: Imagine you write some piece of software. The calculations that must be done to run your software is dependend on your input value. Let's say, x describes how many possible combinations of streets you must compare for your car's navigation system to get from A to B and this number will not be linear but will be described by some function, e.g. 6x^4 - 2x^3 + 5 (Wikipedia example). Then for large x you will not bother too much about the 2x^3 part of this function anymore since then 6x^4 grows way much faster and will mostly determine what you need to compute.

    Now we do some simple math:

    |6x^4 - 2x^3 + 5| \le 6x^4 + |2x^3| + 5\\<br />
                                      \le 6x^4 + 2x^4 + 5x^4\\<br />
                                      = 13x^4\\<br />
                                      = 13|x^4|

    Now for high x this function will less and less differ from its (somehow least) upper bound (in power). And usually you are mostly interessted what will happen for large x since this is time you actually worry about. (You do not wanna wait for hours for your route to be computed.) So you summerize all these function in a common class so it becomes easier to stress that they somewhat belong together and all they will need to have in common to be "similar" is the upper bound (not considering the multiplicational factor (13) since again, this is not too important for large numbers and we don't want to bother if e.g. 12x^4 is an upper bound too (that is even lower).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2010
    Posts
    3
    thank you ivleph and raphw. i really appreciate your help. just have one more question. both of you added all the terms using the highest exponents to get the constant C which was 4 in the original example and 13 in the example that raphw provided. Now im trying to relate that to the following example from the book:

    (this is just a continuation of the original example i provided).....

    (paraphrased from the textbook)....

    alternatively, we can estimate the size of f(x) when x > 2. when x > 2, we have 2x < x^2 and 1 < x^2. consequently, if x > 2, we have 0 < x^2+2x+1 < x^2+x^2+x^2 = 3x^2. it follows that C = 3 and k = 2 are also witnesses to the relation f(x) is O(x^2)

    I understand that we only need to find ONE pair of witness and since we already determined from original example that 4 and 1 are witnesses to this relationship, there are many other pairs of witnesses. once again, i understand the logic but can't figure out how the book gets 3x^2 from.

    i guess the part that im confused at is, i understand how in original example we got x^2+2x+1 < x^2 +2x^2 +x^2 = 4x^2. but for the same terms, we now have x^2+2x+1 < x^2+x^2+x^2 = 3x^2 this time when x > 2.

    Thanks again in advance!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2010
    Posts
    86
    However, here we have the additional assumption: 2x < x^2 and x > 2 > 1 which is why we can solve as the book did. Not that it would make much of a difference for the actual result. This is valid for all n > 2
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2010
    Posts
    3
    Quote Originally Posted by raphw View Post
    However, here we have the additional assumption: 2x < x^2 and x > 2 > 1 which is why we can solve as the book did. Not that it would make much of a difference for the actual result. This is valid for all n > 2
    thanks again!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by lvleph View Post
    O(h) essentially means that the quantity goes to zero at the same rate as h. Or that the quantity is similar in magnitude as h.
    Nonsense, f(x)\in O(g(x) means that as x \to \infty

    \dfrac{|f(x)|}{g(x)}

    is bounded. That means that |f(x)| grows no faster (up to a multiple) than $$ g(x)

    Hence if f(x)\in O(x) then f(x) \in O(x^n) for all n\ge 1. In other words O(x)\subseteq O(x^n) for all n\ge 1

    (with some qualification and abuse of notation big-O notation can be adapted for x approaching other values)

    CB
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Mar 2009
    Posts
    378
    Quote Originally Posted by lvleph
    O(h) essentially means that the quantity goes to zero at the same rate as h.
    Quote Originally Posted by CaptainBlack View Post
    That means that |f(x)| grows no faster (up to a multiple) than $$ g(x)
    How are these really different? Sure I suppose it doesn't necessarily imply anything about going to zero, but in applied mathematics (which is my field, we always think about things going to zero or the true solution). The important portion of what I was saying was that the portion about rates.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by lvleph View Post
    How are these really different? Sure I suppose it doesn't necessarily imply anything about going to zero, but in applied mathematics (which is my field, we always think about things going to zero or the true solution). The important portion of what I was saying was that the portion about rates.
    One says the relevant ratio goes to zero, while the other makes no such assertion but only claims it does not grow beyond some value.

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: March 10th 2011, 03:23 AM
  2. nCr notation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2010, 11:51 AM
  3. Notation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 4th 2010, 12:36 PM
  4. Replies: 1
    Last Post: August 26th 2009, 01:40 PM
  5. Notation
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: March 27th 2009, 09:26 PM

Search Tags


/mathhelpforum @mathhelpforum