algorithms – Meaning of “running time is $O(n^2)$”

We say that a function $f(n)$ is $O(n^2)$ if there exist constants $C,N>0$ such that $f(n) leq Cn^2$ for all $n geq N$. We usually denote “$f(n)$ is $O(n^2)$” by “$f(n) = O(n^2)$“.

An algorithm has running time $O(n^2)$ if its worst-case running time is $O(n^2)$. That is, if we denote by $T(n)$ the maximum running time of the algorithm on inputs of length $n$, then the algorithm has running time $O(n^2)$ if $T(n) = O(n^2)$.

Equivalently (and this is the point of the CLRS formulation), an algorithm has running time $O(n^2)$ if there exists some function $f(n) = O(n^2)$ such that the running time of the algorithm on an input of length $n$ is always at most $f(n)$.

If we denote the running time of the algorithm on the input $x$ by $T(x)$, and the length of $x$ by $|x|$, then we can see the difference between these two equivalent definitions by writing them out formally.

The first definition is
$$
max_{|x| = n} T(x) = O(n^2),
$$

where the left-hand side defines a function of $n$, which we denoted above by $T(n)$.

The second definition states that for some $f(n) = O(n^2)$,
$$
T(x) leq f(|x|).
$$

If the second definition holds, then in particular
$$
max_{|x|=n} T(x) leq f(n),
$$

and so
$$
max_{|x|=n} T(x) = O(n^2),
$$

which is the first definition.

If the first definition holds, then we can take $f(n) = max_{|x|=n} T(x)$ to obtain a function satisfying the second definition:
$$
T(x) leq max_{|y|=|x|} T(y) = f(|x|),
$$

where the first definition guarantees that $f(n) = O(n^2)$.