4 ms·
wouldn't that be O(N^2) because it takes longer to sweep your hand over the spaghetti if there is more spaghetti?
by JoshuaDavid 8y ago
wouldn't that be O(N^2) because it takes longer to sweep your hand over the spaghetti if there is more spaghetti?
- lainga 8y agoWell, really, it's more like O(n) cutting, O(m) sweeping (rather than O(1)) in the largest value m we are trying to sort, and thus the time it takes for your hand to go from the highest spaghetti to the table, and O(n) picking spaghetti out. In that sense it's like radix sort, but you could make a similar point for comparison-based sorts as well, e.g. sorting 1024-bit numbers on a certain-width architecture will take longer, because you need more operations per comparison. I think the point of the example is that lining the pieces up so that they can be picked out is constant-time, because they are physical objects and all either being pushed or falling under their own gravity. That's a good point, though, it assumes arbitrarily large (Andre the Giant?) hands.
- whatshisface 8y agoIf a Turing machine can have an infinite tape then a spaghetti pusher can have infinite palms.