4 ms·
No, the runtime complexity is just hidden in the scheduler of your OS
by bananasbandanas 8y ago
No, the runtime complexity is just hidden in the scheduler of your OS
- johnfn 8y agoI don’t think this fully resolves the problem. If you had n computers and had each of them sleep for one of the numbers, and then append to a shared list, you could sort in O(n) without a scheduler. My favorite part about this algorithm is that you can speed it up by a factor of k - for any k! - by simply dividing the time you sleep by by k.