4 ms·
Would the algorithmic runtime of this be O(N)?
by diabeetusman 8y ago
Would the algorithmic runtime of this be O(N)?
- bananasbandanas 8y agoNo, the runtime complexity is just hidden in the scheduler of your OS
- johnfn 8y agoI don’t think this fully resolves the problem. If you had n computers and had each of them sleep for one of the numbers, and then append to a shared list, you could sort in O(n) without a scheduler. My favorite part about this algorithm is that you can speed it up by a factor of k - for any k! - by simply dividing the time you sleep by by k.
- deleted 8y ago[deleted]
- cal97g 8y agoTechnically yes... rather genius if you only care about cpu time and not real return time.
- saurabh20n 8y agoComparison-based sorts have O(1) complexity on the size of the elements being sorted. I.e., comparison between two numbers is a single instruction assuming numbers fit within a word. Even if you assume very very large numbers then comparison would be O(k), where k is number of bits needed to represent a number. So a more accurate runtime of O(nlogn) algorithms should be O(k.nlogn). The runtime of this algorithm is O(n.2^k).
- deleted 8y ago[deleted]
- mortehu 8y agoThe O(N log N) best case only applies to comparison sorts. What's described here is not a comparison sort, and could easily be made O(N) with radix sort if the size of the numeric type is constant.
- deleted 8y ago[deleted]