Results 1 to 8 of 8

Math Help - Witnesses for Big O

  1. #1
    Newbie
    Joined
    Feb 2006
    Posts
    18

    Witnesses for Big O

    I am very lost right now when it comes to finding witnesses for big O relationships. The problem says the following:

    To establish a big O relationship, find witnesses C and k such that
    | f(x) | <= C | g(x) | whenever x > k


    Determin whether each of these functions is O(x^2)

    a) f(x) = 17x + 11

    First of all, I am not sure if this is a O(x^2) function. I believe it is not because the function is not quadratic therefore it cannot be a O(x^2) function.

    b) f(x) = x^2 +1000

    This function is clearly a O(x^2) function. Now as for solving for C and k, I have no idea how to do.

    I do not understand what is C and k, and what do they do.

    Looking at "| f(x) | <= C | g(x) | whenever x > k"

    f(x) is the function given
    g(x) is the x^2 in "O(x^2)" right?

    so for part b)

    x^2 +1000 <= C(x^2)

    now if k = 1 x>k so x can be 2 and that gives 1004 <= C*4
    so C can be 251?


    Thank you for your help!
    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 hotmail590
    I am very lost right now when it comes to finding witnesses for big O relationships. The problem says the following:

    To establish a big O relationship, find witnesses C and k such that
    | f(x) | <= C | g(x) | whenever x > k


    Determin whether each of these functions is O(x^2)

    a) f(x) = 17x + 11

    First of all, I am not sure if this is a O(x^2) function. I believe it is not because the function is not quadratic therefore it cannot be a O(x^2) function.
    First if f(x)=O(x^n) for some n then f(x)=O(x^m), for all  m\ge n

    In order to show that f(x)=O(x) it is sufficient to find the witnesses.

    Now lets find the witnesses. Lets assume C=1, so now we seek
    an k such that:

    <br />
|17x+11|\le|x^2|\  \forall\  x>k<br />

    Now just by sketching the two functions involved it is clear that if for some
    x_0>0,\ x_0^2>17x_0+11 then  x^2>17x+11 for all x>x_0.

    Now try x_0=1,000, x_0^2=1,000,000, and 17x_0+11=17,011,
    so 1,000 will do for for our witness k.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by hotmail590
    b) f(x) = x^2 +1000

    This function is clearly a O(x^2) function. Now as for solving for C and k, I have no idea how to do.

    I do not understand what is C and k, and what do they do.

    Looking at "| f(x) | <= C | g(x) | whenever x > k"

    f(x) is the function given
    g(x) is the x^2 in "O(x^2)" right?

    so for part b)

    x^2 +1000 <= C(x^2)

    now if k = 1 x>k so x can be 2 and that gives 1004 <= C*4
    so C can be 251?
    You need to show that:

    <br />
x^2+1000 \le C x^2<br />

    for all x>1 with the value of C you have choosen.
    Now when x=1.1, the LHS of the inequality is 1001.21, and the
    RHS is C(1.1)^2, which is less than the LHS if C=251.

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2006
    Posts
    18
    Thank you very much for your reply CaptainBlack!

    Some questions I have:

    For the first part a), I see that you have started by trying a value for k such as 1000 and then working your way to get C. Following your example, I tried to solve b) again. This time I used k as 1000 and came up with

    | x^2 +1000| <= Cx^2 if x= 1001 then

    1003001 < C(1002001)

    and figured out C can be 100.

    So I get k = 1000 and C = 100


    Would it be also correct if C was any number larger than 100 such as 1000 or 10,000 or 99,999,999,999?


    There are many differnt values for k and C for these types of problems (more than one answer) right?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by hotmail590
    Thank you very much for your reply CaptainBlack!

    Some questions I have:

    For the first part a), I see that you have started by trying a value for k such as 1000 and then working your way to get C. Following your example, I tried to solve b) again. This time I used k as 1000 and came up with

    | x^2 +1000| <= Cx^2 if x= 1001 then

    1003001 < C(1002001)

    and figured out C can be 100.

    So I get k = 1000 and C = 100


    Would it be also correct if C was any number larger than 100 such as 1000 or 10,000 or 99,999,999,999?


    There are many differnt values for k and C for these types of problems (more than one answer) right?
    Yes, that's right. The object is to find an example of a k and C that will
    serve as witnesses, so we look for a case that is easy for us.

    (You should also provide at least some explanation anout why the inequality
    holds for any x>k -it being obviouse is ofen good enough )

    RonL
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Feb 2006
    Posts
    18
    Another question on the following problem:



    http://i43.photobucket.com/albums/e3...0/untitled.jpg

    What do those 2 symbols mean? The ones around the x's that look like half brackets



    Many thanks again CaptainBlack for the help!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,063
    Thanks
    370
    Awards
    1
    Quote Originally Posted by hotmail590
    Another question on the following problem:



    http://i43.photobucket.com/albums/e3...0/untitled.jpg

    What do those 2 symbols mean? The ones around the x's that look like half brackets



    Many thanks again CaptainBlack for the help!
    In case it's convenient here's the LaTeX for the above expressions:
    \lfloor x \rfloor
    \lceil x \rceil

    -Dan
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by topsquark
    In case it's convenient here's the LaTeX for the above expressions:
    \lfloor x \rfloor
    \lceil x \rceil

    -Dan
    They are the floor and ceiling functions.

    \lfloor x \rfloor denotes the floor of x, the greatest
    integer less than x.

    \lceil x \rceil denotes the ceiling of x, the smallest
    integer greater than x.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. False witnesses
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 21st 2009, 08:14 PM

Search Tags


/mathhelpforum @mathhelpforum