Run time estimate of a butterworth filter

I am completely new to the field of DSP -- so this question may be
elementry

I was wondering about the worst case performance of a butterworth
bandpass filter. I know that the FFT algorithm has a worst case
performance of O(N log N). Does a second order bandpass filter have a
similar computational cost? How does this cost vary as a function of
the order of the filter?

Any insight would be grately appreciated.

Thanks,

Arctan

<arctan.spam.mail@gmail.com> wrote in message
news:1115747323.151598.31410@o13g2000cwo.googlegroups.com...
> I am completely new to the field of DSP -- so this question may be
> elementry
>
> I was wondering about the worst case performance of a butterworth
> bandpass filter. I know that the FFT algorithm has a worst case
> performance of O(N log N). Does a second order bandpass filter have a
> similar computational cost? How does this cost vary as a function of
> the order of the filter?

With an FFT, you have a block of data of N samples.  So assuming you want to run
a Butterworth bandpass filter on the same block of N samples, the cost would be
O(N).

If the filter is higher order, it is still an O(N) algorithm, though the actual
cost is increased linearly (i.e. the constant multiplier is higher for higher
orders).  Now if you assume that N is the order of the filter rather than the
length of the block of samples to filter, then when you filter a fixed block,
the filter cost is O(N) again, i.e. cost increases linearly with increasing
filter order.

arctan.spam.mail@gmail.com wrote:
> I am completely new to the field of DSP -- so this question may be
> elementry
> 
> I was wondering about the worst case performance of a butterworth
> bandpass filter. I know that the FFT algorithm has a worst case
> performance of O(N log N). Does a second order bandpass filter have a
> similar computational cost? How does this cost vary as a function of
> the order of the filter?
> 
> Any insight would be grately appreciated.
> 
> Thanks,
> 
> Arctan
> 
A second-order filter will require, at most, 5 multiplies, a first-order 
3.  For an N-order filter you'll want to break it down into as many 
first-order filters as you can, with only the resonant pole-pairs being 
second order (an N-order butterworth filter has zero or one first-order 
sections, and floor(N/2) 2nd-order sections).

-------------------------------------------
Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Arctan wrote (by the way, did you know that Lem names his humanoid
robots in "The Invincible" Arctan?):

>I was wondering about the worst case performance of a butterworth
>bandpass filter. I know that the FFT algorithm has a worst case
>performance of O(N log N). Does a second order bandpass filter have a
>similar computational cost? How does this cost vary as a function of
>the order of the filter?
>
>Any insight would be grately appreciated.

You're not comparing apples to apples.

Fast convolution (FFT) filtering uses O( (N+M) (log (N+M) + 1) ) time
to run M samples through an FIR of order N, as compared to time domain
convolution which uses O( N M ) for the same process. If you want to
run M samples through a IIR butterworth filter of order N, then this
also takes O(  N M ) time.

However, depending on the filter requirement, the N for a FIR and the N
for an IIR implementation will vary strongly. Also, depending on your
programming capabilities and the hardware platform, the constants that
we have ignored so far can make a big difference. Furthermore, the
computation time of the fast convolution filter algorithm can be tuned
in a streaming application (by selecting M appropriatly) such that the
constants become small (this again depends on the hardware available,
cache, memory, etc.). And lastly, there is no "worst case" for
computing filters. It's a deterministic process.

Regards,
Andor