title: Basic Complexity Question - Convolution
body: <p>I'm trying to evaluate the complexity of some basic image filtering algorithms. I was wondering if you could verify this theory;</p>
  
  <p>For a basic pixel by pixel filter like Inverse the number of operations grows linearly with the size of the input (In pixels) and </p>
  
  <p>Let S = Length of the side of the image
  Let M = # pixels input</p>
  
  <p>Inverse is of order O(M) or O(S^2).</p>
  
  <p>A convolution filter on the other hand has a parameter R which determines the size of the neighborhood to convolve in establishing the next pixel value for each filter.</p>
  
  <p>Let R = Radius of convolution filter</p>
  
  <p>Convolution is of order O(M*((R+R*2)^2) = O(M*(4R^2) = O(MR^2)</p>
  
  <p>Or should I let N = the size of the convolution filter (Neighbourhood) in pixels?</p>
  
  <p>O(M*(N)) = O(MN)</p>
  
  <p>Ultimately a convolution filter is linearly dependent on the product of the number of pixels and the number of pixels in the neighbourhood.</p>
  
  <p>If you have any links to a paper where this has been documented it would be greatly appreciated.</p>
  
  <p>Kind regards,</p>
  
  <p>Gavin</p>