Convolution

Applying FIR filters to input signals is computationally expensive. There are $N$ inputs that need to be transformed into $N$ outputs. Each of the $N$ outputs depends on all of the $N$ inputs. This means that the computational complexity of applying a FIR filter is $O(N^2)$. However, it turns out that there is a faster way to compute FIR filters that relies on the Convolution Theorem.