When the size of your image doubles (say from 300×400 to 600×800), the number of pixels goes up by 4 times.  Now, if your algorithm compares every pixel of one image with every other pixel of the other, the number of comparisons (of function evaluations) should go up by 16 times.

This is for a straight comparison. If, suppose your algorithm also compares the neighboring 2% height and 2% width (say), then this factor should be even much more. ...If, on the other side, you take some short-cut, like use some average pixel values, the factor should be somewhat less.  This depends on the algorithm you adopt.

Hope this explains the complexity of your approach !