4 ms·
You can replace the hand with any device that holds the spaghetti. This really is an O(n) algorithm. Spaghetti sort seems to be an analogue variant of radix so
by madmax96 7y ago
You can replace the hand with any device that holds the spaghetti. This really is an O(n) algorithm.
Spaghetti sort seems to be an analogue variant of radix sort.
- FartyMcFarter 7y agoI suppose one could add a step 0 to the algorithm: 0: Manufacture a pair of hands big enough to hold all the spaghetti you'll need in the later steps. Does this step take linear time as well?
- madmax96 7y agoDoes it take O(n) time to manufacture computer memory? I don’t know, but it doesn’t affect the runtime of algorithms.
- FartyMcFarter 7y agoBut many sorting algorithms work in-place, so they don't require extra memory beyond a small O(1) or O(log n) amount for bookkeeping. When algorithms do require extra memory, they state this requirement as the space complexity.
- random_savv 7y agoI came here to write this comment. Glad somebody beat me to it! +1