3 ms·
Exactly. Radix sort isn't really linear. It is O(N * M) where N is the size of the collection and M is the number of possible items in the collection. If the nu
by kevincox 5y ago
Exactly. Radix sort isn't really linear. It is O(N * M) where N is the size of the collection and M is the number of possible items in the collection. If the number of possible items is fixed (like fixed-size integers) then it is effectively linear. However you can do this with strings just the same way.
- __s 5y agoYou 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.
- oriolid 5y agoWhy M? The whole point of radix sort is to do the comparisons binary digit by digit so that the total number becomes O(N * log(M)).
- kevincox 5y agoOops, you are right. I was thinking the entropy/bits of the possibilities but accidentally wrote number.
- deleted 5y ago[deleted]