So if I have an image of the size: 1920×1080 and I want to apply a convolution filter of 3x3. Take the formula for DFT $N^2$ and FFT $N \log N$. What should I fill in for N in this case?
Your image is M rows x N cols, and a 2D FFT requires 1D FFTs on all rows followed by 1D column-wise FFTs on the result.
So you have:
$M N \log N + N M \log M = MN (\log M + \log N) = MN \log MN$
operations in total.
The DFT case can be derived using a similar method - this is left as an exercise for the reader.
In DFT-FFT operation the N stands for Number of samples you have in that Sequence.
For example If you have matrix function like with 3*3 order then It means in the first sequence you got 3 Samples and in the second sequence you got 3 samples.
Here stood for the number of samples in the given function sequence.