Comment by schobi

If we look at the example of the FFT blur filter, sure O(n) looks easier and independent of the blur size, but you have an overhead in needing FFT and iFFT. It can be faster for some sigmas, but not for all. So you need different variants depending on sigma and a smooth transition between them.

Then you can start approximating - for large sigmas just using every 10th pixel would work. Looks like MS Teams background blur is doing this, you get a blurry background with aliasing - yay!

Once you add SIMD variants and look at CPU caching behaviour, you build versions for different CPUs. Instead of filtering the whole image for one dimension you might finish blocks locally.

You've now got a dozen variants that need testing and maintenance on different architectures.

I'm reminded of my colleague preaching requirements engineering - what was the goal gain?