3 ms·
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
by perlgeek 16y ago
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 16y agoNot 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 16y agoThat'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.