# Big oh notation

• Nov 6th 2012, 04:48 AM
Nora314
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?
• Nov 6th 2012, 05:12 AM
Prove It
Re: Big oh notation
Quote:

Originally Posted by Nora314
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*}.
• Nov 6th 2012, 05:41 AM
Nora314
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|?
• Nov 6th 2012, 07:21 AM
Nora314
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?
• Nov 6th 2012, 10:12 AM
emakarov
Re: Big oh notation
Quote:

Originally Posted by Nora314
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.
• Nov 6th 2012, 03:03 PM
Prove It
Re: Big oh notation
Quote:

Originally Posted by Nora314
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.