DFT/FFT: What did N stand for again? 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.