Is it correct to say that a linear algorithm is $O(n^2)$?
Formally yes — $O$ is only an upper bound, so every $O(n)$ function is also $O(n^2)$ — but it is a true statement that conveys almost nothing, which is why the tightest bound is the one you quote.
* O is only a ceiling, so the classes nest — every looser bound above the tight one is also true. *
The definition asks only for $f(n) \le c \cdot g(n)$ beyond some $n_0$. A linear $f$ comfortably satisfies that with $g(n) = n^2$, so the claim is valid. It is the same kind of truth as "this file is under a terabyte": correct, useless.
Hence the conventions around writing an O-bound:
| Write | Not | Why |
|---|---|---|
| $O(n)$ | $O(n^2)$ for a linear algorithm | state the tightest bound you can justify |
| $O(n)$ | $O(3n + 5)$ | drop constants and lower-order terms — the notation already ignores them |
| $O(n^2)$ | $O(n^2 + n)$ | keep only the dominant term |
The common confusion worth naming: people read "$f$ is $O(g)$" as "$f$ grows like $g$". It says "no faster than". If you want "exactly this rate", the notation for it is $\Theta$ (Theta), which bounds from above and below; and $\Omega$ (Omega) bounds only from below. In everyday use, "this algorithm is $O(n^2)$" is nearly always meant as $\Theta(n^2)$ — but the formal distinction is what makes statements like "an $O(n)$ algorithm is also $O(n^2)$" both correct and unhelpful.
Go deeper:
Big O notation — the Bachmann–Landau family — where O, Θ, Ω and little-o differ, stated precisely.