How to calculate the computational complexity of filtfilt low-pass filter?

I have a signal 'x' of length N which I perform lowpass filtering with matlab filtfilt. a and b are filter coefficients.

Is it possible to calculate its complexity in terms of Big O like O(...)?

y = filtfilt(b,a,x)

Answer 1

[Bruno Luong]

filtfilt just do twice (forward + backward) the filter. In your case it is IIR, where the complexity is

O((length(a)+length(b))*N)

[Kalasagarreddi Kottakota]

@Bruno Luong,

Thank you, May I aks you: how did you arrive this formula?

One more query. Some time I see using filtfilt like filtfilt(h,1,x), especailly for box filter. Then in this case it is O(length(h)*N)?

[Bruno Luong]

You can read the More about in the doc https://www.mathworks.com/help/matlab/ref/filter.html, difference equation and count the numerb of operaions. For each time step it requires O(length(a)+length(b)) operations.

filter or filtfilt always works with a and b, not directly with h. Input h is just for different and convenient user interface.

[Kalasagarreddi Kottakota]

Hi @Bruno Luong,

Can you confirm if it is O(length(a)*length(b)) or O((length(a)+length(b)))? like * or +.

In your 1st reply you had '+' and second one you had '*'.

[Bruno Luong]

Plus

O(N*(length(a)+length(b)))

[Kalasagarreddi Kottakota]

Thank you @Bruno Luong