Proving Big Oh Notation 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$
 A: 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.
A: 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.
A: 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$
A: 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).$$
