Hey, Bart --- The complexity of the rolling-max algorithm we discussed is always O(N) to process N samples. Using the algorithm from the paper Ross linked, the worst case for a single sample is O(w); with Ethan Fenn's binary-search modification, the worst case complexity for one sample is O(log2(w)). So scaling the window size is fairly cheap, especially with Ethan's variant. This algorithm can find maximum and/or minimum.
If a linear search is not performed prior to the binary search, the amortized complexity of the rolling-max algorithm becomes something like O(N*log2(w)). It's a bit hard to explain why without illustration. A max-tree will consistently take O(log2(w)) per sample in the worst case (where samples of increasing value are supplied). Thus the worst-case complexity for N samples is O(N*log2*w)). – Evan Balster creator of imitone <http://imitone.com> On Mon, Jul 25, 2016 at 12:18 AM, Bart Brouns <b...@magnetophon.nl> wrote: > Hi, OP here. > > > Unfortunately I don't understand all you are saying, due to my lack of C > and Z-transform skills. > > This is what I understood, please correct me if I'm wrong: > - My algo is called a binary max-tree. (When used with max as an > operator) > - The other algo discussed is faster on average, but has spikes that are > higher. > > > Some questions: > > - IIUC, none the other algos mentioned can cheaply vary the window size > at run-time, right? > - None of them generalize for other binary operators instead of max, > right? (mine works for any operator that is associative and > commutative) > - Can I further optimise this algo by doing a linear search for the > first log2(w) samples? Why? How? > > > Many thanks, > Bart > _______________________________________________ > 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
