BilateralFilter complexity

edit

Without having seen the implementation, my guess is that it's image_size * filter_size, i.e. n²*m², like for "regular" filtering.

A few weeks ago, I stumbled upon a paper that claimed a O(1) filter (with certain restrictions for the filter), but I don't know the details.