Ahh, smart! Thanks for the insight; I understand now.
It occurs to me that you could slightly tighten the bound on per-sample
work, because it's not necessary to include the elements of the linear
search in the binary one. The worst-case would then be O(J) per sample,
where J=log2(w-J). But
The trick is to count the total number of operations, not for each incoming
sample as the window moves.
The algorithm maintains a buffer that pushes at the back and pops at both front
and back. Each sample is pushed onto the buffer and popped out of it exactly
once. If R samples are popped
Yeah, with a binary search, you're doing O(log(w)) work, but you might not
end up discarding any samples. With the paper's linear search, you might do
O(w) work, but only if you end up discarding O(w) samples. So, it turns out
to be worth it, as long as you can tolerate the spike.
The thinking
From: music-dsp-boun...@music.columbia.edu
[mailto:music-dsp-boun...@music.columbia.edu] On Behalf Of Liam Sargent
Sent: 20 July 2016 23:11
To: music-dsp@music.columbia.edu
Subject: [music-dsp] Music applications/DSP online masters
Hello all,
Been subscribed to this list for a while
