FFT versus Direct Convolution

The following table compares the number of operations needed to perform the convolution of two length $N$ sequences for various values of $N$ :

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 (adapted from [244]), the FFT (software) beats direct time-domain convolution at length 128 and higher. It takes approximately $N^2$ multiply/add operations to calculate the convolution summation directly, while it takes on the order of $N\cdot$   log$_2(N)$ operations to use the FFT method. (Note, by the way, that $H(\omega_k)$ can be calculated once in advance for time-invariant filtering operations.)

In digital audio, FIR filters are often hundreds of taps long. For such filters, the FFT method is much faster than direct convolution in the time domain.