Results 1 to 11 of 11

Math Help - Big O Notation

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    1

    Big O Notation

    Hello all,

    I've read some of the previous posts in regards to the Big O Notation and this seems to remain my achillies heel in terms of discrete math.

    The given function is my book is this:

    |f(x)| <= C|g(x)| when x > k (as I've seen on other posts as well).

    My confusion comes from the first example in the book, given here:

    Show that f(x) = x^2 + 2x + 1 is O(n^2).

    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. Consequently, we can take C = 4 and k = 1 as witnesses. That is f(x) = x^2 + 2x + 1 < 4x^2 whenever x > 1.

    Alternately, we can estimate 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, C = 3 and K =2

    End Solution

    I don't really understand the x > 1, x < x^2 and 1 < x^2 when x > 1 part, nor do I seem to understand how they reach x^2 + 2x^2 + x^2. Same goes for x > 2.

    Anyone able to explain the above?

    Thanks!

    W
    (First post!)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Wiredg View Post
    Hello all,

    I've read some of the previous posts in regards to the Big O Notation and this seems to remain my achillies heel in terms of discrete math.

    The given function is my book is this:

    |f(x)| <= C|g(x)| when x > k (as I've seen on other posts as well).

    My confusion comes from the first example in the book, given here:

    Show that f(x) = x^2 + 2x + 1 is O(n^2).

    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. Consequently, we can take C = 4 and k = 1 as witnesses. That is f(x) = x^2 + 2x + 1 < 4x^2 whenever x > 1.

    Alternately, we can estimate 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, C = 3 and K =2

    End Solution

    I don't really understand the x > 1, x < x^2 and 1 < x^2 when x > 1 part, nor do I seem to understand how they reach x^2 + 2x^2 + x^2. Same goes for x > 2.

    Anyone able to explain the above?

    Thanks!

    W
    (First post!)

    If x>1 then x^2>x>1, since

    Suppose:

     <br />
x>1<br />

    multiply both sides by x to get:

    x^2>x


    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2009
    Posts
    5

    Big O notation question

    hi, I am weak in big-O notation too.

    I do don't think u have explicitly addressed the "how they reach x^2 + 2x^2 + x^2" part of the question.

    Also, after the explanation of x>1, where did the 0 in "0 <= x^2 + 2x + 1 <= x^2 + 2x^2 + x^2 = 4x^2" come from??

    thank you so much for taking your time to answer this question.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2009
    Posts
    7
    Here is what you have to think about when it comes to Big O notation.

    f(x)<=C*g(x)

    C is a constant that is bigger than 0 and x > k. For it to be big O, then for all x that is greater than k, this equation has to hold true.

    So for this: f(x) = x^2 + 2x + 1 is O(x^2).

    You get: x^2 + 2x+ 1 <= C*x^2, if you remove the x^2 from the left side, you get 2x+1 <= (C-1)*x^2. You know that x^2 has a higher order of growth than 2x, so as x continues to get larger, x^2 will be bigger than 2x+1. As for C, you can pretty much just pick whatever number that works, the same for k. The important thing is that this has to be true for every possible x value greater than k, not just 1 value.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2009
    Posts
    5
    hi daibotcom, i understand your explanation. But i still cannot follow the example given by the first poster.

    "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 <= = 4x^2 whenever x > 1. Consequently, we can take C = 4 and k = 1 as witnesses. That is f(x) = x^2 + 2x + 1 < 4x^2 whenever x > 1.
    "

    First, what does it mean " we can readily estimate the size of f(x) when x>1 ? why can't we readily estimate the size of f(x) when x=1 or x<1 ?

    CaptainBlack has done an excellent job in explaining how we get x<x^2 and 1<x^2.

    However, I do not understand the part that comes after "It follows that...."
    Specifically, where did x^2 + 2x^2 + x^2 come from and how can it later become x^2 + x^2 + x^2 ?

    Please help.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Apr 2009
    Posts
    7
    "Specifically, where did x^2 + 2x^2 + x^2 come from and how can it later become x^2 + x^2 + x^2 ?"

    You just make it up, you just need to make up some expression that would make the inequality true. x^2 + 2x^2 + x^2 was just made up, it equals 4x^2, so for that inequality, the 4 would be the "constant". And then you just need to find a number that x has to be bigger than, and no matter how much bigger that x is from the number you chose, the expression is always true.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2009
    Posts
    5
    isn't there a systematic manner to go about looking for C and k instead of just making up expressions?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Apr 2009
    Posts
    7
    You can always try simplifying the equation or adding terms, there isn't a set way to do it. The definition gives you a lot of room to do what you want to get it to work, there isn't a specific answer that works, there are tons.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Apr 2009
    Posts
    5
    so if we can simply make up equations, what use is C and k in big O notation?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Apr 2009
    Posts
    7
    You come up with the equations based on the C and k values you make up. These problems aren't ones where you just go in and solve for 1 answer and that is the only correct one, you are just looking for a C and k value that makes the inequality true, if it makes it true for all x > k for a given C, then you proved the definition.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Apr 2009
    Posts
    5
    Thks for the explanation, really appreciate it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum