Re:Sleep sort (2011)
by davrosthedalek on Friday December 26, 2014 @03:14AM
(#8798422)
You can always scan through the array, rescale everything by 1/max(input). Then the sleep part is O(1) and the scan part is O(n) -> O(n) total.
[ Parent
| on HN ]
Re:Sleep sort (2011)
by JoshTriplett on Friday December 26, 2014 @03:23AM
(#8798447)
Division isn't O(1) for arbitrary values (potentially larger than a machine word).
The same is true for comparison though, isn't it?