News for hackers. Stuff that matters.
Re:Sleep sort (2011) by gpfault on Friday December 26, 2014 @02:53AM (#8798390)
It's more like O(max(input)), not O(n) (see the first response)
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.
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).
Re:Sleep sort (2011) by pdw on Friday December 26, 2014 @04:24AM (#8798526)
The same is true for comparison though, isn't it?
Re:Sleep sort (2011) by dalke on Friday December 26, 2014 @09:28AM (#8798893)
Sleep maxes out at 2147483647 = 2^31 seconds. Generally these problems assume the transdichotomous model, where the machine word size matches the problem size.
Re:Sleep sort (2011) by fennecfoxen on Friday December 26, 2014 @10:42AM (#8799076)
Well. Let's distinguish between computational complexity and wall-clock time. The code you write yourself here performs operations with O(n) asymptotic complexity where n is the number of elements, but the system scheduler may be able to find additional work to do while the algorithm is waiting to resume, or even put the CPU into a lower-energy state.

Of course, making lots of system calls to create processes and store them in your operating system's process table almost certainly invokes operations with greater than O(n) asymptotic complexity, but this complexity is still unrelated to max(input).