2D Image Convolution: Spatial Domain vs. Frequency Domain Convolution in the Computational Complexity Sense I want to convolve 2 images I1 and I2. Let's assume they have the same size.
I know 2 methods:
1) Use direct definition of 2D convolution
2)  i. Computer FFT of I1 (call it I1_FFT) and FFT of I2 (call it I2_FFT)
   ii. Multiply I1_FFT and I2_FFT (call it I1I2_FFT)
  iii. Compute inverse FFT of result I1I2_FFT

I want to know the number of multiplications and additions for each case.  Note I don't want the Big O type of complexity.

It would be great if the answer includes a derivation.

In the end, I want to know for a specific NxM sized image, when I should use method 1 or 2.
Vanilla implementation of each method for image of size m x n and kernel of size k x l will yield:


Spatial Domain Convolution - O(mnkl) as for each pixel in the image we do kl multiplications (Additions are discarded).
Frequency Domain Convolution - O(mn log(mn) + mn) as the complexity of the FFT is mn log(mn) and we add the multiplication (You could add factor of 4 for doing it twice and back and forth).


But in practice there many nuances:


Many times the kernel is Separable or can be approximated by 1-2 separable filters (For instance, Gaussian Filter).
If the kernel is very small compared to the image, better use direct method.
If you apply the same filter on many images you may even consider using Matrix Form (As done in CNN's).
In Frequency Domain you apply Convolution with Circular Boundary Condition. It means that if you're after different boundary conditions you'll need to pad and then complexity is higher and many memory operations are done.


I can go on and on...

You may have a look at Filtering n×n Images by Separable m×m Filters. Computation Time for Filtering Using FFT, 2D Convolution and Two 1D Convolutions.

In order to say which is better, one must be very specific about the case.
In most cases, use efficient spatial domain code. This is my choice in most cases.