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