News for hackers. Stuff that matters.
Re:Locating the Source of a Mysterious Beep by peri-cl on Monday November 09, 2026 @11:14PM (#50435994)
Yes, but that's also O(log n) physical effort. This one's O(1) sitting on your butt.

(Solely for entertainment purposes: I think "physical binary search" is more properly O(n^{1/3} log(n)), or maybe O(n^{1/2} log(n)). Because real objects have sizes, and moving things (or moving between things) takes time proportional to distance).

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

Re:Locating the Source of a Mysterious Beep by MisterMunchkin on Tuesday November 10, 2026 @01:15AM (#50436712)
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.