For one wedge, the worst case is a monotonic signal, which will saturate the wedge with R samples.
For two wedges, the worst case is the situation where the absolute distance from previous samples to the latest sample is monotonically decreasing. In this case the wedges will contain R+1 samples between them (because the latest sample always appears in both). – Evan Balster creator of imitone <http://imitone.com> On Fri, Sep 2, 2016 at 12:36 PM, Ethan Duni <ethan.d...@gmail.com> wrote: > Right aren't monotonic signals the worst case here? Or maybe not, since > they're worst for one wedge, but best for the other? > > Ethan D > > On Fri, Sep 2, 2016 at 10:12 AM, Evan Balster <e...@imitone.com> wrote: > >> Just a few clarifications: >> >> - Local maxima and first difference don't really matter. The maximum >> wedge describes global maxima for all intervals [t-x, t], where x=[R-1..0]. >> >> - If two equal samples are encountered, the algorithm can forget about >> the older of them. >> >> It has been very helpful for my purposes to visualize the algorithm thus: >> Imagine drawing lines rightward from all points on the signal. Those >> which extend to the present time without intersecting other parts of the >> signal form the minimum and maximum wedge. The newest sample, and only the >> newest sample, exists in both wedges. >> >> [image: Inline image 3] >> http://interactopia.com/archive/images/lemire_algorithm.png >> >> The algorithm can safely forget anything in grey because it has been >> "shadowed" by newer maximum or minimum values. >> >> – Evan Balster >> creator of imitone <http://imitone.com> >> >> On Fri, Sep 2, 2016 at 1:50 AM, Ross Bencina <rossb-li...@audiomulch.com> >> wrote: >> >>> On 2/09/2016 4:37 PM, Ross Bencina wrote: >>> >>>> When the first difference is positive, the history is trimmed. This is >>>> the only time any kind of O(N) or O(log2(N)) operation is performed. >>>> First difference positive implies that a new local maximum is achieved: >>>> in this case, all of the most recent history samples that are less than >>>> the new maximum are trimmed. >>>> >>> >>> Correction: >>> >>> [The new local maximum dominates all >>>> history up to the most recent *history sample* that exceeds it, which is >>>> retained.] >>>> >>> >>> I had said "most recent local maximum" but the history contains a >>> monotonic non-increasing sequence. >>> >>> Ross. >>> >>> _______________________________________________ >>> 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 >> > > > _______________________________________________ > 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
