I'm given the following proof but I have problems with it:
Suppose that $f \in O(n)$ then by definition there exist $c \in R^+$, $m \in N$ such that $f(n) \geq cn$ for all $n \geq m$. We therefore have $f(n)^2 \geq c^2n^2$ for all $n \geq m$. Therefore we conclude that $f \in O(n^2)$
My first confusion is that I was taught that to have $f(n) \in O(g(n))$ we need this $f(n) \leq c*g(n)$ to be true. However here we have $f \in O(n)$ therefore $f \leq c n$ and not $f \geq cn$ like mentioned in the proof. Why is that?
My second confusion is what does $m$ have to do here? Why do we need it?
My third confusion is why the last sentence of the proof concludes that $f \in O(n^2)$ but we wanted to demonstrate $f^2 \in O(n^2)$
Confusion 1: I think there is a typo in that proof. I think it should be $f(n) \le cn$ and $f(n)^2 \le c^2n^2$.
Confusion 2: The definition of $f(n)\in O(g(n))$ is there is some $c \in \mathbb{R}^+$ and some $m \in \mathbb{N}$ such that $\forall n \gt m, f(n) \le cn$.
The role $m$ plays is that $f$ can do whatever it wants up till $m$ and then, after $m$, it is less than $cn$. The reason is that big-O is meant to look at behavior for big inputs $n$ - its not so concerned with small values. E.g. $f(n) = 1000n + n^2 \in O(n^2)$ because even though for small values of $n$ the linear term dominates, eventually it becomes meaningless.
Confusion 3: The proof does show that $f(n)^2 \in O(n^2)$ - its just that the last sentence is that $f(n) \in O(n^2)$ (which does follow).