Proving that $f(n) \not\in O(n)$ given that $f(n) \in \Theta(n^2)$ and the formal definitions of Big-Oh and Theta
Since $f(n) \in \Theta(n^2)$ there exist two constants $n_0$ and $c&gt;0$ such that $f(n) \ge c n^2$ for all $n \ge n_0$.
Suppose then that $f(n) \in O(n)$. For some $n'_0$ and $c'&gt;0$, we have
$f(n) \le c'n$ for all $n \ge n'_0$.
Selecting $n = \max\left\{ n_0, n'_0, 1+\left\lfloor \frac{c'}{c} \right\rfloor \right\}$ leads to the following contradiction:
$$
c' n\ge f(n) \ge c n^2 \ge c \cdot \left(1+\left\lfloor \frac{c'}{c}\right\rfloor\right) \cdot  n &gt; c \cdot \frac{c'}{c} \cdot n = c'n.
$$