# Why autocorrelation can be more efficiently calculated using the fft

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

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