4 ms·
It's constant with respect to the number of elements, just not the maximum magnitude of those elements.
by recursive 3y ago
It's constant with respect to the number of elements, just not the maximum magnitude of those elements.
- upon_drumhead 3y agoI don't see how it is. Different, but the same number, of elements is a different time. There's no constant time between [0, 1] and [0, 10], both having two elements.
- squeaky-clean 3y ago[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] is just as fast as [9] If you really want to make it strictly constant time, just append INT32_MAX to the end of the array before sorting, and then pop it after.
- deleted 3y ago[deleted]
- libealistand 3y agoOh yeah, because assumin maximum values in your domain doesn't move all algorithms into constant time and renders complexity theory void.
- squeaky-clean 3y agoIt doesn't though. How would merge sort become constant time if you assume a maximum value? It's also a joke...
- libealistand 3y agoThe main "value" in the domain of sorting problems is the number of elements in your collection. A subproblem also considers the elements to be integers, then they become another "value" domain. (But in general, sorting problems only need their elements to be comparable, not necessarily integers.)