Re:Spaghetti Sort (2018)
by bashinator on Sunday September 29, 2019 @11:39PM
(#21111593)
Aha so a sleep sort is translating the operation into the time domain In essentially the same way that spaghetti sort translates into the spatial domain! Thank you.
For sleep sort, the time taken is a constant function of the size of the list; it only depends on the value of the maximum element of the list. T = max(list) + smaller terms associated with scheduling timeouts. So, it's O(max(list)). Although, the "smaller terms" I'm ignoring blow up when the size of the list exceeds your computer's resources. I'd guess that spaghetti-sort is O(sum(list)).