2
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ sorry (i feel really stupid now) is there a simpler explanation than that? $\endgroup$ – phoenixWright Jul 27 '14 at 5:57
  • $\begingroup$ I guess it depends on what you have studied. You have taken calculus right? Also, what's your definition of the $O$ notation? $\endgroup$ – Gina Jul 27 '14 at 6:05
  • $\begingroup$ I haven't. This is for discrete math and what it says on our book is that there exists 2 pair of witnesses C and k such that f(n) <= C(g(n)) whenever n > k $\endgroup$ – phoenixWright Jul 27 '14 at 6:10
  • $\begingroup$ @Phoenix: I see. If you did not have calculus yet, you won't have some powerful theorem for asymptotic estimate like this. However, as long as you know that polynomial with highest degree coefficient being positive will become always positive at sufficiently large $n$ then that's good enough. $\endgroup$ – Gina Jul 27 '14 at 6:19
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.