Contributed by Louis-Guillaume Gagnon
- Consider a convolution operation over continuous functions: . Using the definition of the Fourier transform and its inverse , show that taking the inverse transform of the product of two fourier-transformed functions yields the convolution of these functions in their original domain.
- For discrete functions over a finite domain, what is the time complexity of the regular, time-domain-only convolution operation? What is the time complexity of a convolution implemented using the Fourier transform?
- Using the programming language of your choice (e.g. python with numpy), empirically verify your results of 2).