Also, if your convolution kernel is short enough, you can beat an FFT. So, in 2D with an NxN image, an FFT filter will have a complexity of about (N^2 + N^2 Log N). If your kernel is KxK, then direct convolution will be (N^2 K^2), so you have to compare Log N with K^2. But keep in mind 1.) these are asymptotic complexities the coefficients matter 2.) K may or may not depend on N 3.) FFTs are may have larger memory requirements, although you may be able to get away with in-place FFTs, and you don't have to explicitly compute the FFT of the gaussian - you can work that out analytically (you should get another gaussian...).

Also, as someone pointed out, the gaussian is separable, so then the complexity of the direct convolution is (K N^2).

Anyway, what are FFT libraries like for iOS? I suppose with Apples policies, you can't compile FFTW for your App?