Proof for $f(n) \in O(n)$ implies $[f(n)]^2 \in O(n^2)$.

Question

I'll first give my proof:

$$f(n) \in O(n) \implies f(n) \leq c \cdot n$$

with $c \in \mathbb R^+$ and $n \geq m$ with $m \in \mathbb N$.

Let $f(n) = b \cdot n$ with $b \in \mathbb R^+$

$$[f(n)]^2 \in O(n^2) \implies b^2 \cdot n^2 \leq c \cdot n^2$$

There exists a $c \geq b^2$ therefore $f(n) \in O(n)$ implies that $[f(n)]^2 \in O(n^2)$. $\square$

Is my proof correct; if not what is wrong? Can someone also give me a correct proof?

Answer 1

First, note you should use absolute values around $f(n)$ in the inequality, such as shown in the Formal Definition section of Wikipedia's "Big O notation" article. Also, you've only shown it's true for a specific $f(n)$, i.e., $f(n) = bn$.

To show it's true in general for all $f(n) \in O(n)$, note that, since $cn \gt 0$, you have for $n \ge m$ with $m \in \mathbb{N}$ your expression that you can square both sides to get

$$|f(n)| \le cn \implies |f^2(n)| \le (c^2)n^2 \tag{1}\label{eq1A}$$

This shows that $[f(n)]^2 \in O(n^2)$, with the constant being $c^2$ in this case.