# Why autocorrelation can be more efficiently calculated using the fft

Can anyone explain why autocorrelation can be more efficiently calculated using the fft ?

## 1 Answer

Bcause the FFT is computed usingn $$N\log N$$ arithmetic operations, whereas the DFT using $$N^2$$ operations, where $$N$$ is the number of points in your discrete-time signal. So the number of operations is much lower if $$N$$ is particularly high, which is often the case ...

Watch this video if you want to know more about this https://www.youtube.com/watch?v=iTMn0Kt18tg

• you've compared FFT to DFT, I would suggest for better understanding of readers instead of DFT refer to autocorrelation itself. – MimSaad Aug 6 at 0:59