[perlgeek]

If you talk about O(something(n)) run times there's an implicit agreement that you are talking about worst case behavior.

And the worst case of bogosort is not to terminate.

[cdavid]

Not sure about that: qick sort is generally said to be O(NlogN), but its worst case is O(N^2) (the simple implementation anyway).

[sesqu]

That's an abuse of notation. Quicksort is expected O(N log N), where the expectation is usually over a uniform distribution of all permutations.

The actual notation for proportional asymptotic dominance of expectation is too convoluted for use, so people just don't use one. But to even leave out the word "expected" is just plain wrong.