0

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.

arkeet
  • 6,695
Hani
  • 11
  • 1
    Wait, so you've already shown that $\frac{n^{2}+1}{n+1} \leq n$ for all $n\geq 1?$ Does this not fit your definition of $\frac{n^{2}+1}{n+1} = O(n)$ as $n\to\infty,$ with $n_{0}=1$ and $C=1?$ What is left to show? – Will R Sep 25 '16 at 22:13
  • You see, the two answers you received so far are more complicated than yours -- so indeed, what are you asking? – Did Sep 25 '16 at 22:24

4 Answers4

3

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.

Adriano
  • 41,576
1

$$\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)$$

Dan Robertson
  • 2,959
  • did you use C=1 ? – Hani Sep 25 '16 at 21:45
  • 1
    I used a combination of the definition of big-O notation ($O(f(n))=g(n)$ as $n\to\infty$ means that ...) and the fact that knowing that definition and a few simple rules coming from it (e.g $kn=O(n)$ or $O(n^a)+O(n^b)=O(n^{\max(a,b)}$) that allow one to solve this type of problem quickly and intuitively – Dan Robertson Sep 25 '16 at 22:01
0

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

AlgorithmsX
  • 4,560
0

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.

JMP
  • 21,771