On: Locating the source of a mysterious beep

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>.

EDIT: 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!

O(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