2.3.6 Fast Fourier transform FFT From Eq(2.234)it is clear that 1) For each value of k, the direct computation of X(k requires 4N real multiplication and (4N-2) real additions X(h must be computed for n different values of k the direct computation of the discrete Fourier transform of a sequence x(n) requires 4N2 real multiplications and N(4N-2 )real additions or alternatively, N2 complex multiplications and N(N-1) complex additionsFrom Eq. (2.234) it is clear that 1) For each value of k, the direct computation of X(k) requires 4N real multiplication and (4N-2) real additions. 2) X(k) must be computed for N different values of k, the direct computation of the discrete Fourier transform of a sequence x(n) requires 4N2 real multiplications and N(4N-2) real additions or, alternatively, N2 complex multiplications and N(N-1) complex additions. 2.3.6 Fast Fourier transform (FFT)