Lets say I have a image of $NxN$ and a separable filter that I want to apply on it. there are 2 ways to do that: 1. By convolution in spatial domain. 2. By multiplication in frequency domain.
I need to analyze which way is better (depands on A).
My calculations so far:
for the first way: naive convolution will take $(NxN)*(AxA)$ multiplication operations and $A*(NxN)$ addition operations. i.e. $O(N^2A^2)$. Now, we can use the fact that the filter is separable: For each cell in the image we can only multiply 2A cells of the filter. We will get: $(NxN)*(2A)+O(2A)(NxN) = O(N^2A)$.
for the second way: we will do the operations in the frequency domain-
To calculate FFT of the image we will pay $O(NlogN)$.
To calculate FFT of the filter we will pay $O(NlogN)$ [I am not sure about that..].
Point-to-point multiplication of the filter and the image will cost $NxN$. Calculate inverse FFT of the result image will cost $O(NlogN)$. Summing it up: $O(NlogN)$.
I guess that I have mistakes because in my result it is clear that the the second way is cheaper but I know that it depands on A.
can someone help me?