Results 1 to 6 of 6
Like Tree3Thanks
  • 1 Post By Prove It
  • 1 Post By emakarov
  • 1 Post By Prove It

Math Help - Big oh notation

  1. #1
    Member
    Joined
    Nov 2011
    Posts
    87

    Red face Big oh notation

    Hi everyone!

    I just want to say before my question that I love this forum so so much, I have gotten a lot of help, and you people deserve a noble price for being so smart and helpful and nice.

    For my question, I have another question about big-oh-notation, I am finally starting to understand the concept of it better, but I still struggle with some fundamental problems.

    So, the problem is:

    Show that (x2 + 1) / (x + 1) is O(x)

    My book really has no good explanation on how to think when trying to find a constant C and k for which this is true. I thought maybe someone here would know a fancy way to do it?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,831
    Thanks
    1602

    Re: Big oh notation

    Quote Originally Posted by Nora314 View Post
    Hi everyone!

    I just want to say before my question that I love this forum so so much, I have gotten a lot of help, and you people deserve a noble price for being so smart and helpful and nice.

    For my question, I have another question about big-oh-notation, I am finally starting to understand the concept of it better, but I still struggle with some fundamental problems.

    So, the problem is:

    Show that (x2 + 1) / (x + 1) is O(x)

    My book really has no good explanation on how to think when trying to find a constant C and k for which this is true. I thought maybe someone here would know a fancy way to do it?
    \displaystyle \begin{align*} \frac{x^2 + 1}{x + 1} &= \frac{x^2 + x - x + 1}{x + 1} \\ &= \frac{x^2 + x}{x + 1} + \frac{-x + 1}{x + 1} \\ &= \frac{x(x + 1)}{x + 1} + \frac{-x - 1 + 2}{x + 1} \\ &= x + \frac{-x - 1}{x + 1} + \frac{2}{x + 1} \\ &= x + \frac{-(x + 1)}{x + 1} + \frac{2}{x + 1} \\ &= x - 1 + \frac{2}{x + 1}\end{align*}

    Now to show \displaystyle \begin{align*} \frac{x^2 + 1}{x + 1} \in O(x) \end{align*}, we need to show that \displaystyle \begin{align*} \left| \frac{x^2 + 1}{x + 1} \right| \leq M|x| \end{align*} for some \displaystyle \begin{align*} M \in \mathbf{R} \end{align*}.

    \displaystyle \begin{align*} \left| \frac{x^2 + 1}{x + 1} \right| &= \left| x - 1 + \frac{2}{x + 1} \right| \\ &\leq |x| + |-1| + \left| \frac{2}{x + 1} \right| \\ &= |x| + |1| + \frac{|2|}{|x + 1|} \\ &< |x| + |x| + 2|x| \textrm{ for large positive values of }x \\ &= 4|x| \end{align*}

    Since \displaystyle \begin{align*} \left| \frac{x^2 + 1}{x + 1} \right| \leq 4|x| \end{align*}, we can say \displaystyle \begin{align*} \left| \frac{x^2 + 1}{x + 1} \right| \in O(x) \end{align*}.
    Thanks from Nora314
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2011
    Posts
    87

    Re: Big oh notation

    Thank you so so much for the wonderful explanation! I went through it, and I believe I understand how to solve this exercise now. I just have a few questions, if you don't mind, which I think will help me clear things up completely.

    What you do in the first part of the exercise, where you turn x2 + 1 / x + 1 into x - 1 + 2/x + 1, is it that you try to write the original expression in terms of x and not x2, because we are trying to see if it is O(x)?

    Also, when you write the whole new expression in terms for the largest positive value of x, and it becomes : 4|x|, why do you turn |2| / |x + 1| into 2|x| and not just |x|?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2011
    Posts
    87

    Re: Big oh notation

    Also, if you don't mind, could you help me with another question?

    The question is:

    Give a big-O estimate for n(log(n2 + 1)) + n2 log n

    I thought a good estimate would be n2 since this is the biggest power of n , and this function changes faster than log n, but the answer in the answer key is: "O(n2 log n),
    I don't understand why the answer is not just n2, why is it necessary to add log n when n2 will always change the fastest?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Big oh notation

    Quote Originally Posted by Nora314 View Post
    Give a big-O estimate for n(log(n2 + 1)) + n2 log n

    I thought a good estimate would be n2 since this is the biggest power of n , and this function changes faster than log n, but the answer in the answer key is: "O(n2 log n),
    I don't understand why the answer is not just n2, why is it necessary to add log n when n2 will always change the fastest?
    n2 surely changes faster than log n, but the problem is that log n is unbounded from above. You cannot say that n2log n <= Cn2 for all n from some point on regardless of how large the constant C is because eventually log n exceeds C.
    Thanks from Nora314
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,831
    Thanks
    1602

    Re: Big oh notation

    Quote Originally Posted by Nora314 View Post
    Thank you so so much for the wonderful explanation! I went through it, and I believe I understand how to solve this exercise now. I just have a few questions, if you don't mind, which I think will help me clear things up completely.

    What you do in the first part of the exercise, where you turn x2 + 1 / x + 1 into x - 1 + 2/x + 1, is it that you try to write the original expression in terms of x and not x2, because we are trying to see if it is O(x)?

    Also, when you write the whole new expression in terms for the largest positive value of x, and it becomes : 4|x|, why do you turn |2| / |x + 1| into 2|x| and not just |x|?
    Yes, you are trying to get the highest power of your quotient. You could use long division instead if you liked.

    You could use |x| if you wanted to.
    Thanks from Nora314
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. notation.
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: May 21st 2011, 02:43 AM
  2. Replies: 1
    Last Post: March 10th 2011, 03:23 AM
  3. Set notation
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: February 9th 2011, 04:58 AM
  4. Big Oh notation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 16th 2010, 04:27 AM
  5. Replies: 1
    Last Post: August 26th 2009, 01:40 PM

Search Tags


/mathhelpforum @mathhelpforum