Re:Locating the Source of a Mysterious Beep
by akoboldfrying on Tuesday November 10, 2026 @12:02AM
(#50436271)
Good point about the moving effort required. But if moving an object takes constant time, then it's O(n) overall -- since even though there are O(log n) steps, among all n-1 non-beeping items, either (i) all are moved exactly once (this case occurs when the beeping item is not moved during the initial halving) or (ii) half are never moved and the other half are moved exactly twice for O(2 * n/2) = O(n) work, and this term dominates the log n term.
[ Parent
| on HN ]
Re:Locating the Source of a Mysterious Beep
by peri-cl on Tuesday November 10, 2026 @12:28AM
(#50436440)
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 is O(n)
O(n^{3/2}) if the project is growing out of control and walking distances start to matter
O(n^{4/3}) if that, but somehow it's taking place in 3-dimensions