2 ms·
If you read the actual proofs, they count comparisons, not operations, when they arrive at O(nlogn). More advanced material analyses algorithms on random access
by adrianN 5y ago
If 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