Results 1 to 6 of 6

Math Help - Big-O

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    5

    Big-O

    When it comes to Big-O notation, I draw a blank. I have the question:

    Use the definition of "f(X) is O(g(x))" to show that 2x+17 is O(3x)

    and i'm just wondering if anyone could help me get started
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Oct 2008
    Posts
    51
    Okay. As for the definition, it informally says: 'f(x) is (or belongs to) O(g(x)) if, for all numbers bigger than some arbitrary number A the growth of g(x) is faster than or as fast as f(x)'s.'

    Since the formal definition includes a constant, most authors would simply ask you to prove that 2x + 17 is O(x).

    Nevertheless, to conclude your proof all you must do is show some real number x_0 such that 2x + 17 <= 3x, x > x_0

    EDIT: Jhevon correctly pointed out that you need to specify where x is going. As the most common application of Big O is to show assymptotical domation of one funcion over another, I assumed x \rightarrow \infty

    Hope this helps,
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    5
    Find witnesses C and k such that |f(x)| ≤ C|g(x)| whenever x > k
    Use the definition of

    f(X) is O(g(x)) to show that 2^x+17 is  O(3^x)

    I've never truly understood Big-O, so i don't know where to start.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2008
    Posts
    51
    Quote Originally Posted by Numbah51 View Post
    Find witnesses C and k such that |f(x)| ≤ C|g(x)| whenever x > k
    Use the definition of

    f(X) is O(g(x)) to show that 2^x+17 is  O(3^x)

    I've never truly understood Big-O, so i don't know where to start.
    Notice that even though my answer assumed f and g were linear functions, the process is the same: prove that 2^x+17 \leq C3^x, x > x_0, C \in \mathbb{R}.

    To get you a better view, putting the formalist aside a little bit, show that 'eventually 2^x+17 doesn't grow faster than 3^x.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Numbah51 View Post
    Find witnesses C and k such that |f(x)| ≤ C|g(x)| whenever x > k
    Use the definition of

    f(X) is O(g(x)) to show that 2^x+17 is  O(3^x)

    I've never truly understood Big-O, so i don't know where to start.
    choose C = 7 and k = 1
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2008
    Posts
    5
    Thank you guys so much, i understand it now and answered my question. I really appreciate all your help.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum