Ethan --- If we use only a binary search in the discard step, isn't the amortized complexity still O(N)? I suppose not... We'd be doing a log2(w) search every sample in the worst case where a monotonic decrease occurs.
I'll have to look over the paper to get a better understanding, but would be very interested to hear your thought process with the partial linear search. – Evan Balster creator of imitone <http://imitone.com> On Wed, Jul 20, 2016 at 1:23 PM, Dan Gillespie <dgilles...@cosineaudio.com> wrote: > Regarding the Lemire paper his code is provided here: > https://github.com/lemire/runningmaxmin > > It's been a while since I've read the paper, but iirc it reports fast > average O(.), not worst case. Specifically it's good if the signal has few > changes in direction, but the worst case is not better than other > algorithms. > > Dan Gillespie > > _______________________________________________ > dupswapdrop: music-dsp mailing list > music-dsp@music.columbia.edu > https://lists.columbia.edu/mailman/listinfo/music-dsp > >
_______________________________________________ dupswapdrop: music-dsp mailing list music-dsp@music.columbia.edu https://lists.columbia.edu/mailman/listinfo/music-dsp
