2D Image Convolution: Spatial Domain vs. Frequency Domain Convolution in the Computational Complexity Sense
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.