Thread: 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 (x² + 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?

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 (x² + 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?

Now to show , we need to show that for some .



Since , we can say .

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 x² + 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 x², 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|?

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

The question is:

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

I thought a good estimate would be n² 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(n² log n),
I don't understand why the answer is not just n², why is it necessary to add log n when n² will always change the fastest?

Originally Posted by Nora314

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

I thought a good estimate would be n² 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(n² log n),
I don't understand why the answer is not just n², why is it necessary to add log n when n² will always change the fastest?

n² surely changes faster than log n, but the problem is that log n is unbounded from above. You cannot say that n²log n <= Cn² for all n from some point on regardless of how large the constant C is because eventually log n exceeds C.

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 x² + 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 x², 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.