Hacker News Reader

I love the runtime analysis of Spaghetti sort:

> Preparing the n rods of spaghetti takes linear time. Lowering the rods on the table takes constant time, O(1). This is possible because the hand, the spaghetti rods and the table work as a fully parallel computing device. There are then n rods to remove so, assuming each contact-and-removal operation takes constant time, the worst-case time complexity of the algorithm is O(n).

View on HN

Actually I would assume the time for removing each rod while collecting the result is quadratic because when the number of rods is high enough you can no longer see the highest one at a glance but have to scan through all possible rod positions for spotting the one that sticks out.

In spaghetti sort I think you place your hand at the top and remove the first piece to touch it. That takes it from O(n) to O(1) to remove a single piece.

Of course, your hand is then a magical device that can do a reduction in constant time.

Reply on news.ycombinator.com