Computational complexity of Inverse FFT [closed]

StackOverflow https://stackoverflow.com//questions/20022092

Question

I am trying to calculate the computational complexity of ifft, I know it’s NlogN for a N*1 dimension, signal. But I have a product of two signals then I want to get ifft, and then calculate the computational complexity. So simply, if X(w) and Q(w) are Fourier transform of two time signal , then what is computational complexity of their product.
Note: X(w) and Q(w) has same (N*1) size.
ifft(X(w)*Q(w))=???

Was it helpful?

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).

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top