Search code examples
mathbig-osignal-processingfft

Computational complexity of Inverse FFT

I am trying to obtain the computational complexity for the inverse of the fast Fourier transform (IFFT). I already know it’s O(nlogn) for a one-dimensional vector of n positions, but in my case, firstly I have a product of two FFTs. Then, I want to calculate its corresponding IFFT, and obtain its computational complexity.

X(w) and Q(w) are both one-dimensional vectors, and both have n positions.

Simply, if X(w) and Q(w) are FFTs, considering their product is still an FFT (according to the convolution property), what would be the computational complexity of the corresponding IFFT?

Solution

  • It is still O(N log N). The ifft doesn't care how you get the data, and the element-wise multiplication is O(N).