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?
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|?
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?