Good point about the moving effort required. But if moving an object takes constant time, then it's O(n) overall -- since <incorrect argument deleted>.
replyEDIT: My earlier analysis was wrong (it assumed you never move the beeping item after the initial halving), but the conclusion was right for a different reason: Each time you move items, you move half as many as you did last time. You initially move n/2 items, and the geometric series n/2 + n/4 + n/8 + ... + 1 sums to n-1. So O(n) moves are done, and this dominates the log n term for the number of steps.
Yeah, that interpretation is more realistic!
replyO(log n) is if you can split the collection in half in an O(1) step, like, *shoving* the whole pile together as a unit
O(n) if you're moving items one at a time. So, splitting the pile in half once is O(n)
O(n^{3/2}) if the project is way out of control and walking distances start to matter
It’s not sitting on your butt if you have to code an entire system and set up notes throughout the house and monitor them.
reply