2 ms·
All too easy! Relativity tells us that disturbances in the pole cannot move faster than the speed of light. Therefore the time it takes to find out that your p
by mikeash 11y ago
All too easy!
Relativity tells us that disturbances in the pole cannot move faster than the speed of light. Therefore the time it takes to find out that your pole hit something is O(n), since the location of the tallest element will be on average halfway down your line.
Of course, there's the much more obvious problem that "arrange the sticks in a line" requires manipulating each stick, and is thus O(n)!
- darkmighty 11y agoCorrect, of course :) Maybe it's not that good example... I was trying to come up with a way to obfuscate the speed of light limitation (one usually thinks of poles as rigid). A thing I like about those is even if they're really simple they highlight limits like the Bekenstein bound: you can make your experiment arbitrarily large, but if you allow it to shrink arbitrarily (as a function of n), you get unexpected results (essentially BSS machines[1] versus Turing machines?) -- in your example you could actually sort the numbers in O(n). [1] https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smal...