Proving Big Oh Notation

Question

Show that $f(n) = n^{2} + 2n + 1$ is $O(n^{2})$.

Sorry if this is a duplicate question or anything but I'm terribly having a hard time understanding this big-oh notation. I've looked for methods on proving everywhere but I can't seem to understand this part where the $C$ that I'm looking for translated to another function:

$\frac{f(n)}{g(n)} = \frac{n^{2} + 2n + 1)}{n^{2}} < \frac{n^{2} + 2n^{2} + n^{2}}{n^{2}} = 4$

Answer 1

Method without needing calculus:

Set $C=2$. Then $2g(n)-f(n)=n^{2}-2n-1$. This is a degree 2 polynomial with highest coefficicent positive, so there exist a $k$ such that $n^{2}-2n-1\geq 0$ for all $n>k$ which implies that $2g(n)\geq f(n)$ for all $n>k$.

Note that you do not need to find $k$, just need to show that it exists. If you insist on a particular value of $k$, you can find the root of the degree 2 polynomials above. Then you can pick $k=\sqrt{2}+1$.

This method use calculus:

Apply L'Hospital twice (technical details omitted) to get $\lim\limits_{n\rightarrow\infty}\frac{f(n)}{g(n)}=\lim\limits_{n\rightarrow\infty}\frac{f^{\prime}(n)}{g^{\prime}(n)}=\lim\limits_{n\rightarrow\infty}\frac{f^{\prime\prime}(n)}{g^{\prime\prime}(n)}=\lim\limits_{n\rightarrow\infty}\frac{2}{2}=1$. Hence $\limsup\limits_{n\rightarrow\infty}\frac{f(n)}{g(n)}$ is finite, so $f(n)\in O(g(n))$.

Basically, $f(n)\in O(g(n))$ iff $\limsup\limits_{n\rightarrow\infty}\frac{|f(n)|}{|g(n)|}$ is finite.

Answer 2

Choose $C = 3$ and $k = 2$. Then observe that if $n > k = 2$, then: \begin{align*} n^2 + 2n + 1 &< n^2 + 2n + 4 \\ &= n^2 + (2)n + (2)^2 \\ &< n^2 + (n)n + (n)^2 &\text{since $2 < n$} \\ &= 3n^2 \\ &= Cn^2 \\ \end{align*} as desired. $~~\blacksquare$

Answer 3

Note that: $f(n)=(n+1)^2$.

Let $n\geqslant 1$ then $\dfrac{1}{n}\leqslant 1$.

Hence: $$\begin{equation}\begin{split}1+\dfrac{1}{n}\leqslant 2&\Leftrightarrow \dfrac{n+1}{n}\leqslant 2\\&\Leftrightarrow n+1\leqslant 2\cdot n\\&\Rightarrow (n+1)^2\leqslant (2\cdot n)^2\\&\Leftrightarrow f(n)\leqslant 4\cdot n^2\end{split}\end{equation}$$.

Therefore, $$f(n)\in O(n^2).$$

Answer 4

One has $${|n^2+2n+1|\over n^2}\leq 1+{2\over n}+{1\over n^2}\leq 4\qquad(n\geq1)\ .$$ That's all.