DEV Community

loading...

Discussion on: Sleep Sort: Where Theory meets Sobering Reality

Collapse
scionofbytes profile image
Shaun

Correct me but wouldn't this algorithm have o(x) time where x is the largest value in the list? If one of the values is 300,000, that item would be printed 83 hours later.

Collapse
jodydott profile image
Jody Dott

You are correct.

The algorithm is at best O(N) where N is the maximum sized number. However, generally algorithmic analysis is concerned with input size so its EXPONENTIAL with respect to the number of bits in N.

If you are able to modify the algorithm to just take the next highest number, then essentially what you have here is HeapSort developed in a very inefficient way, using OS threads to implement your heap.

So I'd say the algorithm is at least O(N log N) and at worst O(2b N logN) where b is the number of bits in the max number B that may show up in the array.

That is much worse than bubblesort for large B's.

Collapse
perrydbucs profile image
Perry Donham

I was thinking the same thing... O(max(n)), assuming that context switching is significantly smaller than min(n).