FFT Convolution vs. Direct Convolution

Let's compare the number of operations needed to perform the convolution of

2 length $N$ sequences:

• It takes $\approx N^2$ multiply/add operations to calculate the convolution summation directly.

• It takes on the order of $N\cdot$   log$(N)$ operations to compute an FFT. (Note: $H(\omega_k)$ can be calculated in advance for time-invariant filtering.)

N	FFT	Direct Convolution
4	176	16
32	2560	1024
64	5888	4096
128	13,312	16,384
256	29,696	65,536
2048	311,296	4,194,304

In this example (from Strum and Kirk), the FFT (software) beats direct time-domain convolution at length 128 and higher