[...]
Usually, when it is quoted in Big-O notation it should mean "calculated
average over all data sets".
I must disagree. Big-Oh is a statement about some quantity, and
carries no implication about the nature of that quantity: average,
best case, worst case, or whatever. We can say of Quicksort that the
average running time is O(N log N) and the worst is O(N*N), and the
big-Ohs in the two assertions are independent: They are statements
about two different quantities.
In fact, Big-Oh is often used in an entirely different context,
describing a tiny quantity rather than a large one. For example, we
can say that the sum 1/1 + 1/2 + ... + 1/N is ln(N) + O(1). There is
no implication of an average of any kind in this statement, nor even
of a data set or a universe of data sets; there is only a statement
about the rate of growth of the discrepancy between the exact sum
and the approximation.
If notions like "average over all data sets" appear, they do not
arise from the Big-Oh but from the nature of the quantity that Big-Oh
describes. If we're talking about "average," we must describe the
genesis of this average: Over the entire universe of cases or over a
designated subset, weighted or unweighted, time-decayed or static,
whatever. It's not Big-Oh that contributes such things, but the
definition of the quantity under consideration.
Big-O is not really subject to
experimentation, because it is about limits as size tends to infinity.
Or, sometimes, as something tends to zero. You'll find this sense
used all over the place in any textbook on numerical analysis: Integrate
by the trapezoidal rule with step size h and the error is O(h^2); use
Simpson's rule and you can get O(h^4). These Big-Oh's still describe
upper bounds, but the quantities become smaller rather than larger in
the direction of interest.
