Hacker News Reader

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

View on HN

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).

The model I usually consider is a RAM where the word size is ~ logn bits. This seems closest to real computers.

I 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

That article's discussion on HN (6 years ago!) was also quite interesting:

https://news.ycombinator.com/item?id=12383012

M = string length and M = number of different possible values are very, very different. One is the exponential of the other.

Reply on news.ycombinator.com