Hacker News new | past | comments | ask | show | jobs | submit login

Can you explain how sleepsort is constant time when it requires looping through n items?



The runtime is bounded by K, where all numbers you sort are less than K.


From an analysis perspective, I do not believe you can call an O(n) algorithm constant because you could run it on a computer with n cores.

From a practical perspective, I do not believe it is bounded by K, where all numbers you sort are less than K. Consider an array of one hundred trillion items, each being the number 1. This is bounded by the array length, not the number 1.


Realistically, I don't know what the complexity of that algorithm is or if it's possible to have one. Making the argument it is constant time is intended to be a bit of a joke at how difficult it is to give it a time complexity. My interpretation of it as constant time (temporal multiplicand multiplied by the largest value in the list) is going by wall clock time, which is arguably the time that matters in an interview.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: