1. ## 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?

2. ## Re: Big oh notation

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*}.

3. ## 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|?

4. ## 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?

5. ## Re: Big oh notation

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.

6. ## Re: Big oh notation

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.