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.
For example, a naive quicksort takes O(n^2) time. On random data, its expected runtime is O(n lg n). With ideal partitioning, it can be brought down to guaranteed O(n lg n) on arbitrary data, though this will usually make it slower in practice. But someone who says that quicksort is "usually O(n lg n)" is misusing the notation, and hopefully will quickly point this out by mentioning worst-case time.
> 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.)
Big O can be used to represent worst-case behavior, but it can be, and is used also for average-case. And no, it is not a misuse of the notation - it is legitimately used for both (also for best-case, but I have never heard of anybody actually bothering with that). Just be sure to understand which is being talked about.
Okay, this is a subtle point, but you're right. Big-O notation describes an asymptotic upper bound on any function. If that function is average run time, then that's perfectly kosher. Actually establishing what this means, though, is a bit trickier, and something people often mess up.
I don't think it's a subtle point at all - Big-O is not inherently anything to do with worst case time complexity of algorithms, it is a general relationship between functions.
For example, a naive quicksort takes O(n^2) time. On random data, its expected runtime is O(n lg n). With ideal partitioning, it can be brought down to guaranteed O(n lg n) on arbitrary data, though this will usually make it slower in practice. But someone who says that quicksort is "usually O(n lg n)" is misusing the notation, and hopefully will quickly point this out by mentioning worst-case time.
Is this roughly what you had in mind?