4 ms·
"it is a O(N) time complexity sort in all cases" The OS needs to pick which thread to run from a pool of N threads - absolute best case an O(log N) operation,
by al2o3cr 12y ago
"it is a O(N) time complexity sort in all cases"
The OS needs to pick which thread to run from a pool of N threads - absolute best case an O(log N) operation, either when the thread is queued or when it's being selected. This happens N times, so the runtime seems like it would actually scale as O(N log N).
On the other hand, if you've got a scheduler that can pick the thread with the smallest sleep time from a list in O(1) time, you could just use whatever algorithm that's using to make an O(N) insertion sort...
- dspillett 12y agoBut if the time multiplier used is high enough the time spend choosing a thread at each period is small. So while that overhead could increase processing time, wall-clock time need to be affected. Again this is why I think it makes a good example for illustrating critical thinking in the area of algorithm design and analysis. It is an obviously silly example which could actually work, within certain practical boundaries, and the many obvious problems with it are hidden in more complex processes/structures.