State the formal definition of $f(n) \in O(g(n))$.

$f(n)$ is $O(g(n))$ if there are positive constants $c$ and $n_0$ such that $f(n) \le c \cdot g(n)$ for all $n \ge n_0$.

* Below n₀ nothing is promised; from n₀ on, f never rises above c·g again. *

$$f(n) \le c \cdot g(n) \quad \text{for all } n \ge n_0$$

Each piece of that sentence is doing work:

• $c$ — "up to a constant factor". You are allowed to scale $g$ before comparing. This is the formal machinery that makes constants irrelevant.
• $n_0$ — "eventually". The bound may fail for small $n$; it only has to hold from some point on. This is the formal machinery that makes small inputs irrelevant.
• $\le$ — "at most". $O$ is an upper bound, a ceiling, not an exact description.

So the statement "$f$ is $O(g)$" reads: beyond some input size, $f$ grows no faster than $g$, up to a constant factor.

A consequence that catches people out: because it is only a ceiling, a linear function is also $O(n^2)$, and $O(n^{100})$ — all true, all useless. Correctness and informativeness are different things, so the convention is to name the tightest bound you can justify, and to name it in its simplest form: write $O(n)$, not $O(3n + 5)$.

Go deeper:

• Big O notation — formal definition — the definition stated properly, plus the limit forms and the algebra rules.