Re:Spaghetti Sort (2018)
by saagarjha on Monday September 30, 2019 @03:55AM
(#21112723)
It's psuedo-polynomial: https://en.wikipedia.org/wiki/Pseudo-polynomial_time. The Linux scheduler is O(n log(n)) if I remember correctly.
[ Parent
| on HN ]
Re:Spaghetti Sort (2018)
by s_gourichon on Thursday October 03, 2019 @02:41PM
(#21150474)
According to https://en.wikipedia.org/wiki/O(1)_scheduler
> The O(1) scheduler was used in Linux releases 2.6.0 thru 2.6.22 (2003-2007), at which point it was superseded by the Completely Fair Scheduler.
https://en.wikipedia.org/wiki/Completely_Fair_Scheduler
> The fair queuing CFS scheduler has a scheduling complexity of O(log N), where N is the number of tasks in the runqueue. Choosing a task can be done in constant time, but reinserting a task after it has run requires O(log N) operations, because the runqueue is implemented as a red-black tree.