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: https://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.