> Wait, what? Big O notation is all about asymptotic worst-case behavior.
  > Anybody using it in another way is abusing the notation, although it may
  > sometimes be useful to talk that way.

Exactly.

  > For example, a naive quicksort takes O(n^2) time. On random data,
  > its expected runtime is O(n lg n).

Great example. People jump from that to "Quicksort is O(n log n)" + mostly|on average|or something.

Computers today are extremely complex and it's getting worse. Most big-O analysis in textbooks take very misleading assumptions and only apply in a theoretical reduced framework.

For example, continuing the Quicksort case, this algorithm has somewhat unpredictable memory access and comparison results (branch prediction.) Merge sort has a penalty of a lot of memory required (n/2 but it could be mitigated) but it shows very predictable sequential memory access and in many common cases comparisons are predictable (runs of numbers lower on one sequence.) It's easy to apply non-temporal writes, for example. And it's possible to vectorize (thought it's non-trivial.)

Empirical research is the only way.