[pedrocr]

> I suppose Linux has an O(1) scheduler

Actually not anymore. The current CFS scheduler is no longer O(1) but O(logN):

https://en.wikipedia.org/wiki/Completely_Fair_Scheduler