On Thu, Mar 19, 2020 at 8:11 AM Dario Sanfilippo <sanfilippo.da...@gmail.com> wrote:
> > I believe that the time complexity of FFT is O(nlog(n)); would you perhaps > have a list or reference to a paper that shows the time complexity of > common DSP systems such as a 1-pole filter? > The complexity depends on the topology. The cheapest topologies (direct forms) are something like 2*M operations per sample, where M is the filter order. Other topologies are optimized for other properties (such as noise robustness, modulation robustness, etc.) and exhibit higher complexity - generic state-variable topologies can scale as M^2 operations per sample, for example. > If simply comparing two algorithms by the number of operations needed to > compute a sample, would you include delays in filters as an operation? I'm > just wondering as some papers about FFT only include real multiplications > and additions as operations. > Delays usually get accounted as memory requirements in this type of analysis. That isn't to say that copying data around in a real computer doesn't take time, but this is usually abstracted away in the generic DSP algorithm accounting. The underlying assumption being that the DSP throughput is essentially computation bound, and so reducing the total number of MACs is the goal. But that's not terribly appropriate for a software system running on a modern personal computer, for example. Ethan > > Thanks for your help, > Dario > _______________________________________________ > 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
