@alcinnz
Convolution (= same as computing the correlation upside-down and backwards) in regular space is element-wise multiplication in Fourier space.
The transform into fourier space (discrete fourier transform) turns out to be doable with surprisingly few operations, so it's lower complexity to do a Fast Fourier Transform, element-wise multiply, and then do a Fast inverse Fourier Transform back to regular space than compute a correlation in regular space.