2 ms·
[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 bef
by 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.)