4 ms·
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).
by cdavid 15y ago
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 15y 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.