News for hackers. Stuff that matters.
Re:Locating the Source of a Mysterious Beep by bajard on Tuesday November 10, 2026 @04:49AM (#50438076)
You are moving n objects log(n) times, so its O(n.log(n))
Re:Locating the Source of a Mysterious Beep by wky on Tuesday November 10, 2026 @10:03AM (#50441390)
Only half of the remaining boxes need to be moved, not half of the total.
Re:Locating the Source of a Mysterious Beep by nukanse on Tuesday November 10, 2026 @12:49PM (#50443647)
You move n/2, then n/4,...n/2^-i

n. Sum(2^-i)=n

So its o(n. Log(n))

Re:Locating the Source of a Mysterious Beep by bajard on Wednesday November 11, 2026 @05:55AM (#50451942)
Actually,

sum_{i=1}^{log_2(n)} {(n/2^i)} = n - 1

So it's O(n).