News for hackers. Stuff that matters.
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).

There are no comments on this comment yet.