Re:Windows 10 wallpaper was physically built and photographed
by lambdaxyzw on Thursday May 23, 2024 @06:50PM
(#40460832)
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.
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.