>> contact-and-removal operation takes constant time, the worst-case time complexity of the algorithm is O(n).
How is the contact-and-removal operation constant time? How can that assumption ever be true? If you use a parallel processor like human vision or human feel (ie. which pressure nerve activates on the hand) it may appear constant, but if you use a computer it would be n right (as you would need to check n slots). Wouldn't either defy O(n)?
The analog algorithm described is not described for digital computer. It’s an amusing theoretical thought experiment and not a recipe for actual fast sorting. It’s O(n) when you use your hand for contact and removal. I don’t know if it’s possible to implement spaghetti sort on a computer, maybe not, but I guess if it were possible, it would probably at least require n processors to sort n elements. Maybe the nearest analogy on digital computers is radix sort.
Depends on the mathematical framework you're working with.... there's a genre in theoretical compsci that deals with parallel algorithms, and as a toy example, I remember an O(1) sorting algo (given O(n^2) processors). This example is more fun than anything, but ofc in general you're free what constraints you subject your statements to.
You can simplify the "human hand" to a rigid metal sheet that comes down from the top and stops on the highest object. Still constant time, but no "parallel processing" needed.
The point is that reality itself is highly parallel
I wonder if the removal operation is not actually O(sqrt(n)). Depending on the way we structure thought experiment of course. But as the pile of spaghetti gets bigger, the act of picking the largest one is constrained by:
1. how fast your hand can reach for the next spaghetti piece - on average proportional to the radius of the pile of spaghetti, which is proportional to sqrt(n).
2. to actually notice the biggest piece, you need to again wait for a time proportional to sqrt(n) - light propagation is not instant.
So if we start thinking about this algorithm more like a computer scientist would (how fast it is as n grows to the infinity) it doesn't seem to be O(n) IMO.
>> contact-and-removal operation takes constant time, the worst-case time complexity of the algorithm is O(n).
How is the contact-and-removal operation constant time? How can that assumption ever be true? If you use a parallel processor like human vision or human feel (ie. which pressure nerve activates on the hand) it may appear constant, but if you use a computer it would be n right (as you would need to check n slots). Wouldn't either defy O(n)?