Prove $\frac{n^2+1}{n+1}$ is $\mathcal{O}(n)$

Question

I'm trying to proving this formula $\frac{n^2+1}{n+1}$ is $\mathcal{O}(n)$.

As you know we need to come up with $n_0$ and $C$. So I'm confusing a little bit in how to choose a appropriate $C$ since the equation here is division.

For $n > 1$, $n^2+1<n^2+n < n(n+1)$, so $\frac{n^2+1}{n+1} < n$ , for n > 1.

So we proved that for $C = 1, n_0=1:~\frac{n^2+1}{n+1} \leq Cn$ ; ($C=1$)

but I'm stuck here in how to simplest the fraction here.

Answer 1

If $n \geq n_0 = 1$, then: $$ \frac{n^2 + 1}{n + 1} \leq \frac{n^2 + n}{n + 1} = \frac{n(n + 1)}{n + 1} = n = Cn $$ and so we're done.

Answer 2

Use polynomial division. You should get a polynomial plus a rational function.

Answer 3

$$\frac{n^2+1}{n+1}=\frac{(n+1)(n-1)+2}{n+1}=n-1+\frac2{n+1}=O(n)+O(1)+O\left(\frac1n\right)=O(n)$$

Answer 4

To prove $\mathcal{O}(n)$, you need to prove it from both above and below.

Which you (almost) did. If we add an $n^2-1$ argument on the LHS: $$n^2-1\lt n^2+1\le n^2+n = n(n+1)$$

so we have $$\frac{n^2-1}{n+1} \lt \frac{n^2+1}{n+1}\le n$$

$$n-1 \lt \frac{n^2+1}{n+1}\le n$$

and we are done.