Math for sorts, and statements about computational constants which are not time

This is the only article I’ve read that makes sense of the math for me. I especially like the point that we are not talking about time, when we say stuff like “The BubbleSort has a bad worst case scenario.” We are actually talking about computations, and we are only talking about time implicitly, to the extent that we have in our heads an implicit computational model in which the time to do some action, such as comparing 2 keys, is constant.

In computer science and sometimes mathematics, big-O notation is used
to talk about how quickly a function grows while disregarding
multiplicative and additive constants. When classifying algorithms,
big-O notation is useful because it lets us abstract away the
differences between real computers as just multiplicative and additive
constants.

Big-O is not a difficult concept at all, but it seems to be common
even for people who should know better to misunderstand some aspects of
it. The following is a list of misconceptions that I have seen in the
wild.

But first a definition: We write

f(n)=O(g(n))

$$f(n) = O(g(n))$$ when $f(n) \le M g(n)$ for sufficiently large $n$, for some positive constant $M$.

Misconception 1: “The Equals Sign Means Equality”

The equals sign in

f=O(g(n))

$$f = O(g(n))$$ is a widespread travestry. If you take it at face value, you can deduce that since $5 n$ and $3 n$ are both equal to $O(n)$, then $3 n$ must be equal to $5 n$ and so $3 = 5$.

The expression $f = O(g(n))$
doesn’t type check. The left-hand-side is a function, the
right-hand-side is a … what, exactly? There is no help to be found in
the definition. It just says “we write” without concerning itself with
the fact that what “we write” is total nonsense.

The way to interpret the right-hand side is as a set of functions:

O(f)={g∣g(n)≤Mf(n) for some M>0 for large n}.

$$O(f) = \{ g \mid g(n) \le M f(n) \text{ for some \(M > 0\) for large \(n\)}\}.$$ With this definition, the world makes sense again: If $f(n) = 3 n$ and $g(n) = 5 n$, then $f \in O(n)$ and $g \in O(n)$, but there is no equality involved so we can’t make bogus deductions like $3=5$. We can however make the correct observation that $O(n) \subseteq O(n \log n)\subseteq O(n^2) \subseteq O(n^3)$, something that would be difficult to express with the equals sign.

Misconception 2: “Informally, Big-O Means ‘Approximately Equal’”

If an algorithm takes $5 n^2$ seconds to complete, that algorithm is $O(n^2)$ because for the constant $M=7$ and sufficiently large $n$, $5 n^2 \le 7 n^2$. But an algorithm that runs in constant time, say 3 seconds, is also $O(n^2)$ because for sufficiently large $n$, $3 \le n^2$.

So informally, big-O means approximately less than or equal, not approximately equal.

If someone says “Topological Sort, like other sorting algorithms, is O(n log n)”, then that is technically correct, but severely misleading, because Toplogical Sort is also $O(n)$ which is a subset of $O(n \log n)$. Chances are whoever said it meant something false.

If someone says “In the worst case, any comparison based sorting algorithm must make $O(n \log n)$ comparisons” that is not a correct statement. Translated into English it becomes:

“In the worst case, any comparison based sorting algorithm must make fewer than or equal to $M n \log (n)$ comparisons”

which is not true: You can easily come up with a comparison based
sorting algorithm that makes more comparisons in the worst case.

To be precise about these things we have other types of notation at our disposal. Informally:

$O()$:	Less than or equal, disregarding constants
$\Omega()$:	Greater than or equal, disregarding constants
$o()$:	Stricly less than, disregarding constants
$\Theta()$:	Equal to, disregarding constants

and some more. The correct statement about lower bounds is this: “In the worst case, any comparison based sorting algorithm must make $\Omega(n \log n)$ comparisons. In English that becomes:

“In the worst case, any comparison based sorting algorithm must make at least $M n \log (n)$ comparisons”

which is true. And a correct, non-misleading statement about Topological Sort is that it is $\Theta(n)$, because it has a lower bound of $\Omega(n)$ and an upper bound of $O(n)$.