Results 1 to 5 of 5

Math Help - Big-O

  1. #1
    Newbie
    Joined
    Oct 2008
    From
    Lincoln, NE
    Posts
    1

    Big-O

    Hello,

    I'm totally confused by Big-O notation. This is the definition that I was given:

    I don't understand how "k" fits into this equation. I also don't understand the significance of "C" or the relationship between the two constants (or witnesses).

    I'm still thinking through this...

    To prove that f(x) is big-O of g(x), do I just choose an arbitrary value for "C" that makes g(x) larger than or equal to f(x). By arbitrary I mean any value... that I have to prove that works.

    And then for "k"... does that just represent the lower boundary in the domain for that value of "C" that I chose out of thin air. So "k" might actually be some value of "x" that makes f(x) = C ( g(x) ). So all values of x greater than "k" will make C ( g(x) ) greater than f(x).

    My book isn't very clear about any of this and all the information on line contains formulas I don't understand anyways...

    Does anyone have a simple explanation of what the formula means? Is "C" an arbitrary value or is it's value more definitive? What is "k" and what is it's relationship to "C". Right now I'm just guessing..

    Thanks,
    Robert
    Attached Thumbnails Attached Thumbnails Big-O-sdfsd.jpg  
    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 lord_bunny View Post
    Hello,

    I'm totally confused by Big-O notation. This is the definition that I was given:

    I don't understand how "k" fits into this equation. I also don't understand the significance of "C" or the relationship between the two constants (or witnesses).

    I'm still thinking through this...

    To prove that f(x) is big-O of g(x), do I just choose an arbitrary value for "C" that makes g(x) larger than or equal to f(x). By arbitrary I mean any value... that I have to prove that works.

    And then for "k"... does that just represent the lower boundary in the domain for that value of "C" that I chose out of thin air. So "k" might actually be some value of "x" that makes f(x) = C ( g(x) ). So all values of x greater than "k" will make C ( g(x) ) greater than f(x).

    My book isn't very clear about any of this and all the information on line contains formulas I don't understand anyways...

    Does anyone have a simple explanation of what the formula means? Is "C" an arbitrary value or is it's value more definitive? What is "k" and what is it's relationship to "C". Right now I'm just guessing..

    Thanks,
    Robert
    It means that for x large enough f(x) is less than (or equal) some multiple of g(x).


    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    80
    Hello,

    To be precise, you should mention where "x" moves.
    "f(x) is O(g(x)) as x goes to infinity" if there are constants C and k such that |f(x)|<C|g(x)| whenever x>k.
    "f(x) is O(g(x)) as x goes to minus infinity" if there are constants C and k such that |f(x)|<C|g(x)| whenever x<k.
    "f(x) is O(g(x)) as x goes to zero" if there are constants C and k such that |f(x)|<C|g(x)| whenever |x|<k.
    These are used to express the asymptotic behavior of f, and it is common to omit the part "as x goes to ..." if it is clear from the context.
    You usually know that |f(x)| and |g(x)| both go to infinity, but you compare their speed, how fast they grow.

    For example, 2x^2+4x+5=O(x^2) (as x goes to infinity).
    PROOF: Let C=3, k=10. Then, |2x^2+4x+5|<C|x^2| whenever x>k. QED

    Of course, you can choose C=4, k=100 etc., they make no difference, it just says that the terms 4x and 5 are irrelevant compared to the x^2 term.
    Other examples:
    x^n=O(x^m) if n<m.
    (any polynomial of x)=O(e^x).

    Bye.
    Follow Math Help Forum on Facebook and Google+

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

    To be precise, you should mention where "x" moves..
    No, only if you are interested in something other than x large, as the usual definition is for n large.

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Sep 2008
    Posts
    21

    Talking

    hello my friend,

    The big-O method is for approximation of complexity for large X. you can calculate it using limit also. Its to measure the progress of a function when it grows so much and by mean of that, to see how far and how fast a function grows. "C" is a constant and its not considered to have a certain effect on grow, so you can simply ignore it. Just take the largest powers of a function, since a larger power makes a function to grow more faster. it means that if there is f(x) = X^5 + 5X then you have to pick X^5 because it makes the function grows faster than any other element in that equation.
    "k" is where two functions g(x) and f(x) meet eachother and since then,
    g(x) becomes strictly greater than f(x) and by that |f(x)| <= C.|g(x) | for any x which is greater than k.
    I had the same problem understanding this issue. have a look at my post :

    http://www.mathhelpforum.com/math-he...-problems.html

    PEACE and good luck
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum