Results 1 to 6 of 6

Math Help - Big-O

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    4

    Question Big-O

    Hi everyone. Im kind of not seeing it with the follwing problem. Any suggestions is much appreciated.

    Show that (x^2+1)/(x+1) is O(x)

    I was thinking my first step would be
    To use C= 1 and K=1

    but I am stuck here
    Last edited by Ramin_Shahab; July 15th 2008 at 08:35 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2008
    Posts
    792
    What is O(x)? What is C? What is K?

    Can you write out the entire question?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Mathstud28's Avatar
    Joined
    Mar 2008
    From
    Pennsylvania
    Posts
    3,641
    Quote Originally Posted by Chop Suey View Post
    What is O(x)? What is C? What is K?

    Can you write out the entire question?
    It is Big Oh notation, it means that a function is bounded above by whatever. It is usually in discrete mathematics, I believe the K and C are the cosntants you must choose to show that some function is bounded by another. This might be a little bit strange if you have never seen it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2008
    Posts
    4
    Thats pretty much the whole question. But, Im still stuck on this and maybe its the fraction part thats throwing me off. Can anyone please give me somewhere to start?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Ramin_Shahab View Post
    Hi everyone. Im kind of not seeing it with the follwing problem. Any suggestions is much appreciated.

    Show that (x^2+1)/(x+1) is O(x)

    I was thinking my first step would be
    To use C= 1 and K=1

    but I am stuck here

    We say f(x) = O(g(x)),\text{ if }\exists M > 0, \forall x > x_0, |f(x)| < M|g(x)|

    So choose M=1, \forall x > 1, \left|\frac{x^2 + 1}{x+1}\right| < |x|
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Ramin_Shahab View Post
    Hi everyone. Im kind of not seeing it with the follwing problem. Any suggestions is much appreciated.

    Show that (x^2+1)/(x+1) is O(x)

    I was thinking my first step would be
    To use C= 1 and K=1

    but I am stuck here
    For x>0 :

    \frac{x^2+1}{x+1} \le \frac{x^2+1}{x}

    and as for x\ge 1,\ x^2+1 \le 2x^2 ,

    \frac{x^2+1}{x+1} \le \frac{x^2+1}{x} \le \frac{2x^2}{x}=2x


    RonL
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum