What's the big O time-complexity of an IIR filter?

Question

Given an IIR filter like the one shown below, what's its O(n?) time complexity?

I can't decide if it's O(n^2) since to compute each output, you need to iterate through all of the previous samples. But it could also be O(n) because for each output there's only an x number of computations you need (x being the size of b and a), given that you already have all of the previous outputs.

Answer 1

You don’t need to iterate through every sample, only the last k, both for inputs and outputs with the corresponding time lag. So, if you had a second order IIR filter, that would produce 2 coefficient in the nominator and 2 in the denominator (if we’re talking about transfer functions). So, for a filter of order k, there are (roughly) 2k multiplications and additions. That’s for one sample of the output you’re trying to calculate. Now, you apply the filter to a signal of length n, meaning the overall calculation time will rise linearly with k and n, making the full complexity O(k*n).