Advantages of FFT over DFT

 

FFT computation is less complex as compared to the DFT algorithm.

 

DFT Transform 

 

FFT Transform

 

 

 

Fig: FFT Transform of 8 Point DFT

 

 

In the above figure, it is shown that the basic idea of a fast Fourier transform is to break up a transform of length N into two transforms of length N/2.

To compute the DFT of an N-point sequence it take O(N²) multiplies and adds. The FFT algorithm computes the DFT using O(N log N) multiplies and adds.

The fast Fourier transform (FFT) is a discrete Fourier transform algorithm which reduces the number of computations needed for N points from 2N² to 2Nlog₂N.