1 Explain why the Fast Fourier Transform has smaller computa

1. Explain why the Fast Fourier Transform has smaller computational complexity that the discrete Fourier Transform.

2. Write and comment a program that calculates the Discrete Fourier Transform. The comments must be in your own words, and should reflect your understanding of what this algorithm is doing. You might find this explanation helpful: http://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/

3. Find or write (think about recursion, here) a program to calculate FFT. Comment the program in your own words.

Solution

1. Fast Fourier transform is faster and has smaller computational complexity than discrete Fourier Transform because it uses divide and conquer method to solve the computation.

By using divide and conquer it reduces the running time complexity to O(N*log(n)) while DFT has a time complexity of O(N*N) where N is the number of data points . As N gets bigger FFT becomes faster and involve much less computation than DFT.

Since logN increase at a much lower rate than N, the time saved in using the FFT can be considerable. For example, for N = 1024, the ratio of N/logN is about 100. Thus if a 1024 point DFT takes 100 seconds, the FFT on the same data would only take 1 second.