4 ms·
I don’t understand how wall clock time is constant. Sorting [5, 50] is faster wall time then [6, 60].
by upon_drumhead 3y ago
I don’t understand how wall clock time is constant.
Sorting [5, 50] is faster wall time then [6, 60].
- xena 3y agoThe constant is the biggest number in the array
- saagarjha 3y agoIt’s not constant; the algorithm runs in pseudo-polynomial time.
- NotYourLawyer 3y agoIf runtime depends on the input, it’s not constant time.
- recursive 3y agoIt'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.)
- addaon 3y agoIt's constant with regards to the length of the input array, which is the usual metric for sort algorithm performance. That is, d(runtime)/d(len(input)) can be constant, even though d(runtime)/d(max(input)) is not, if you assume that len(input) is independent from max(input) (which is inconsistent with input having uniformly distributed random members, which is probably the more common assumption).