Page 1 of 2 12 LastLast
Results 1 to 15 of 23

Math Help - Big O - Explanation needed

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    32

    Big O - Explanation needed

    I'm reading through a discrete math book and it's talking about Big O notation. The concept makes sense to me, but I don't understand how they're applying it. They give examples and state things to be true and don't explain it.

    An example they give is

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

    This is saying.. what, exactly? Show that the first equation is related to x^2 by use of witnesses? .. I don't even know what that means.


    "Solution: We observe that we can readily estimate the size of f(x) when x>1 because x<x^2 and 1<x^2. It follows that

    0 <= x^2 + 2x + 1 <= x^2 + 2x + x^2 = 4x^2

    whenever x > 1."

    I have no idea what they did here or how they came up with "4x^2". Why would they replace 1 with x^2?

    Any information would be appreciated.
    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jul 2009
    Posts
    152
    Quote Originally Posted by JTG2003 View Post
    I'm reading through a discrete math book and it's talking about Big O notation. The concept makes sense to me, but I don't understand how they're applying it. They give examples and state things to be true and don't explain it.

    An example they give is

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

    This is saying.. what, exactly? Show that the first equation is related to x^2 by use of witnesses? .. I don't even know what that means.


    "Solution: We observe that we can readily estimate the size of f(x) when x>1 because x<x^2 and 1<x^2. It follows that

    0 <= x^2 + 2x + 1 <= x^2 + 2x + x^2 = 4x^2

    whenever x > 1."

    I have no idea what they did here or how they came up with "4x^2". Why would they replace 1 with x^2?

    Any information would be appreciated.
    Thanks
    Apparently there is a typo. They mean:

    x>1\implies x<x^2 and 1<x^2 so that

    0\leq x^2+2x+1 \leq x^2 +2x^2 + x^2 = 4x^2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2009
    Posts
    32
    Quote Originally Posted by AlephZero View Post
    Apparently there is a typo. They mean:

    x>1\implies x<x^2 and 1<x^2 so that

    0\leq x^2+2x+1 \leq x^2 +2x^2 + x^2 = 4x^2.

    Uhm.. I'll keep that in mind .. doesn't seem to clarify much though.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jul 2009
    Posts
    152
    It occurs to me that maybe my above post didn't explain much. So I'll try to flesh things out a bit for you.

    I've seen a few different definitions of Ordo ("Big Oh"), but here's a common one: "Let f(x) and g(x) be nonnegative functions of x. We say that

    f(x) is O(g(x))

    provided that

    f(x)\leq Kg(x)

    for some constant K and x sufficiently large."

    In other words, we need to find a K. In your example, they used simple arguments from inequalities to arrive at K=4. Now that the typo is cleared up, do you see what they did? Post again if you're still confused.

    Cheers.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2009
    Posts
    32
    Quote Originally Posted by AlephZero View Post
    It occurs to me that maybe my above post didn't explain much. So I'll try to flesh things out a bit for you.

    I've seen a few different definitions of Ordo ("Big Oh"), but here's a common one: "Let f(x) and g(x) be nonnegative functions of x. We say that

    f(x) is O(g(x))

    provided that

    f(x)\leq Kg(x)

    for some constant K and x sufficiently large."

    In other words, we need to find a K. In your example, they used simple arguments from inequalities to arrive at K=4. Now that the typo is cleared up, do you see what they did? Post again if you're still confused.

    Cheers.
    Sorry, I'm not really great with math .. I seem to be missing something.

    I know big O notation can be used to describe relationships between algorithms from a computing stand point. So, if you have an algorithm running on an old computer, you can use big O notation to describe how it will run on newer equipment based on constants rather than the numbers being computed.

    This being said, I'm trying to understand the actual meaning of

    Quote Originally Posted by AlephZero View Post
    f(x) is O(g(x))

    provided that

    f(x)\leq Kg(x)
    So, one function (f(x)) is Big O of another function (g(x)) if the first function is less than the second using a constant?

    I seem to be hitting some kind of roadblock here. I see all the inequalities and functions and Big O notations, but I have no idea what they mean.

    I suppose that would be the place to start.

    Unfortunately there seems to have been a TV show called "Big O" and it is clouding all my searches.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jul 2009
    Posts
    152
    Never fear, we'll get it sorted out for you. Okay. You're given a function f(x) and asked to show that it is "Big Oh" another function g(x). This means you need to show there is some constant K, it doesn't matter how large or small so long as it is positive, such that f(x)\leq Kg(x) for x sufficiently large. This last part means "eventually," more or less; in other words, there is a point beyond which any value of x will make the inequality true.

    So in your example, they give you f(x), g(x) is x^2, and " x sufficiently large" is just going to be x>1.

    Now, when x>1, the following inequalities are always true:

    x^2 \leq x^2, \quad 2x<2x^2, \quad 1<x^2.

    This is just how squaring works. You can prove these inequalities in various ways depending on where you are in your math education, but it's good to just know them. If you want to learn how to prove them, post again.

    Now all that's left is to link all these inequalities into a sort of chain, so that

    f(x)=x^2 + 2x +1 \leq x^2 + 2x^2 + x^2 = 4x^2=4g(x).

    Now we've found a K = 4 such that for all x>1, we have f(x)\leq Kg(x), and we're done.
    Last edited by AlephZero; July 31st 2009 at 01:42 PM. Reason: clarity
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Mar 2009
    Posts
    32
    Quote Originally Posted by AlephZero View Post
    x^2 \leq x^2, \quad 2x<2x^2, \quad 1<x^2.

    Ok.. so when x>1, I can see how these are true.

    Quote Originally Posted by AlephZero View Post
    Now all that's left is to link all these inequalities into a sort of chain, so that

    x^2 + 2x +1 \leq x^2 + 2x^2 + x^2 = 4x^2.

    Now we've found a K = 4 such that for all x>1, we have f(x)\leq Kg(x), and we're done.
    Link them in a chain..

    So since
     1 \leq x^2
    then follows that
     x^2 + 2x +1 \leq x^2 + 2x^2 + x^2
    since the 1 in the second part has been replaced with  x^2

    Question 1) Why replace the 1? Because it is a constant and won't have any impact when x is sufficiently large?

    I see what has been done, and that you have created an inequality that is true, but what was the reasoning behind replacing 1 with  x^2 ?



    Question 2) .... still no idea where the  4x^2 came from.
    K is our constant ... but it shows up nowhere in the inequality.
    Does f(x)\leq Kg(x), mean K * g(x)? With g(x) being  x^2 + 2x^2 + x^2 ?

    So we're looking for a number for K that will make this statement true? But I thought it was always true for x>1 ....
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jul 2009
    Posts
    152
    Quote Originally Posted by JTG2003 View Post
    So since
     1 \leq x^2
    then follows that
     x^2 + 2x +1 \leq x^2 + 2x^2 + x^2
    since the 1 in the second part has been replaced with  x^2

    Question 1) Why replace the 1? Because it is a constant and won't have any impact when x is sufficiently large?

    I see what has been done, and that you have created an inequality that is true, but what was the reasoning behind replacing 1 with  x^2 ?

    Question 2) .... still no idea where the  4x^2 came from.
    K is our constant ... but it shows up nowhere in the inequality.
    Does f(x)\leq Kg(x), mean K * g(x)? With g(x) being  x^2 + 2x^2 + x^2 ?

    So we're looking for a number for K that will make this statement true? But I thought it was always true for x>1 ....
    1. We aren't really "replacing" 1 with x^2, we're just proving that 1<x^2. The "linking" of inequalities comes from this rule: a<b, c<d, and e<f implies that a+c+e<b+d+f. So we've taken the three inequalities, and sort of added them together.

    2. We've shown using the inequalites that f(x)\leq 4g(x). Thus we've found a K, which is equal to 4.

    Make sense?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Mar 2009
    Posts
    32
    Quote Originally Posted by AlephZero View Post
    1. We aren't really "replacing" 1 with x^2, we're just proving that 1<x^2. The "linking" of inequalities comes from this rule: a<b, c<d, and e<f implies that a+c+e<b+d+f. So we've taken the three inequalities, and sort of added them together.
    Ok, got it.

    Quote Originally Posted by AlephZero View Post
    2. We've shown using the inequalites that f(x)\leq 4g(x). Thus we've found a K, which is equal to 4.

    Make sense?
     x^2 + 2x +1 \leq x^2 + 2x^2 + x^2


    ... OH. Yes. Kind of. x^2 + 2x^2 + x^2  = 4x^2
    Somehow.. with all these numbers I didn't even realize the second half of the inequality was all x^2's. So.. just combine like terms..

    Ok, so in f(x), x^2 is clearly the driving force. So we compare it to g(x) using only x^2 to derive the constant, 4..?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jul 2009
    Posts
    152
    Quote Originally Posted by JTG2003 View Post
    Ok, so in f(x), x^2 is clearly the driving force. So we compare it to g(x) using only x^2 to derive the constant, 4..?
    Yes, now you've got it. As long as x>1, f(x)=x^2+2x+1 is always going to be less than x^2+2x^2+x^2=4x^2=4g(x). So we've found a constant such that f(x) is eventually always less than this constant multiplied by g(x).

    You're correct that the x^2 is the driving force, because that's our value of g(x). When analyzing f(x), we need to look for how it relates to our g(x).

    I hope that clears it up for you. Please let us know if you're still unsure about something.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Mar 2009
    Posts
    32
    One more thing. What is a "witness"?

    From the book:

    "Consequently, we can take C = 4 and 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."

    Any idea what they're referring to?


    I lied.. another question:

    "Alternatively, we can estimate the size of f(x) when x > 2. When x > 2, we have 2x \leq x^2 and  1 \leq x^2 . Consequently, if x > 2, we have

     0 \leq x^2 + 2x + 1 \leq 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)."


    Again with the witnesses ...



    Are the constants always integers?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jul 2009
    Posts
    152
    Quote Originally Posted by JTG2003 View Post
    One more thing. What is a "witness"?

    From the book:

    "Consequently, we can take C = 4 and 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."

    Any idea what they're referring to?


    I lied.. another question:

    "Alternatively, we can estimate the size of f(x) when x > 2. When x > 2, we have 2x \leq x^2 and  1 \leq x^2 . Consequently, if x > 2, we have

     0 \leq x^2 + 2x + 1 \leq 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)."


    Again with the witnesses ...



    Are the constants always integers?
    1. I've never heard the term "witness" used in this context before (it is sort of novel though... I may consider adopting it), but I know what they mean. Their C is our K, the constant we used to prove f(x)\leq Kg(x), and their k is used in the context of what I called "sufficiently large;" i.e., the inequality we found was true when x>1, and they're calling k=1. (So their "sufficiently large" is something like, "there exists a constant k such that for all x>k, the inequality holds.")

    2. They're doing exactly what we did, except they've found different inequalities to use. Do you understand how they came up with that particular set of inequalities? Post if you don't see why they're true.

    Cheers.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Mar 2009
    Posts
    32
    Yup, got it. I got a little mixed up because we used k instead of C.



    Ok, I'm gonna see if I can finish this section without getting caught op on details for another 4 hours.


    Thanks for your help
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Jul 2009
    Posts
    152
    Quote Originally Posted by JTG2003 View Post
    Yup, got it. I got a little mixed up because we used k instead of C.



    Ok, I'm gonna see if I can finish this section without getting caught op on details for another 4 hours.


    Thanks for your help
    Glad to be of help! Incidentally, I'm sure it's just a caps error, but just to clarify, we used K (in caps) instead of C... so their C is our K and our "sufficiently large" is their k (in lowercase)... just so you don't confuse them.

    Feel free to post again if you need more help on these. Should probably start a new thread, though, as the moderators largely frown on posting multiple problems in a single thread.

    Good luck!
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by JTG2003 View Post
    I'm reading through a discrete math book and it's talking about Big O notation. The concept makes sense to me, but I don't understand how they're applying it. They give examples and state things to be true and don't explain it.

    An example they give is

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

    This is saying.. what, exactly? Show that the first equation is related to x^2 by use of witnesses? .. I don't even know what that means.


    "Solution: We observe that we can readily estimate the size of f(x) when x>1 because x<x^2 and 1<x^2. It follows that

    0 <= x^2 + 2x + 1 <= x^2 + 2x + x^2 = 4x^2

    whenever x > 1."

    I have no idea what they did here or how they came up with "4x^2". Why would they replace 1 with x^2?

    Any information would be appreciated.
    Thanks
    Big-O notation and the other related notations are used to describe the rate of growth of functions. You should know that as x becomes large x^n grows faster than x^r for any r<n. This means that whatever value of k>0 we use, eventually k|x^r|<|x^n|

    When we write:

    f(x)=O(g(x))

    this is short hand (and abuse of notation as well) for f(x) grows no faster than g(x) as x goes to infinity. This means that there is some K such that eventually (that is for all x big enough):

    |f(x)|\le K|g(x)|

    CB
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Permutation Tensor (Explanation Needed)
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: September 14th 2011, 06:37 AM
  2. Explanation needed on a sequence proof
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: June 2nd 2011, 01:30 PM
  3. Function of F(X) Explanation needed.
    Posted in the Algebra Forum
    Replies: 7
    Last Post: January 13th 2011, 12:08 PM
  4. Algebra Explanation Needed
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 31st 2010, 03:55 AM
  5. Multiplication explanation needed
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 7th 2009, 11:46 AM

Search Tags


/mathhelpforum @mathhelpforum