3 ms·
You can also say comparison sorts are O(N * ln N * M) where N is the size of the collection & M is the cost of comparison (eg string length for comparing string
by __s 5y ago
You can also say comparison sorts are O(N * ln N * M) where N is the size of the collection & M is the cost of comparison (eg string length for comparing strings)
But instead we say it requires O(N * ln N) comparisons
- adrianN 5y agoIf you read the actual proofs, they count comparisons, not operations, when they arrive at O(nlogn). More advanced material analyses algorithms on random access machines with some fixed word size for cases where you can't assume that comparisons are constant time operations, or specialize for the data type, e.g. numbers, where you sometimes don't need o(n log n) comparisons at all (like with radix sort).
- pfdietz 5y agoThe model I usually consider is a RAM where the word size is ~ logn bits. This seems closest to real computers.
- __s 5y agoI find this article pretty insightful for thinking about algorithms that involve lots of memory: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
- Radim 5y agoThat article's discussion on HN (6 years ago!) was also quite interesting: https://news.ycombinator.com/item?id=12383012 https://news.ycombinator.com/item?id=12383012
- ccalloway 5y agoM = string length and M = number of different possible values are very, very different. One is the exponential of the other.