When we compute the complexity of an image processing algorithm, we get an $O(N)$.

does the $N$ refers to the number of pixels in the image or to the height/width of the image, I mean it is computed related to $O(nm)$ with $n\times m$ the size of the image ?

please, cite some references.

  • $\begingroup$ What has your literature search turned up? $\endgroup$
    – Bill Barth
    Commented Jul 17, 2015 at 20:27
  • $\begingroup$ I have not find any interesting references :( $\endgroup$
    – user16973
    Commented Jul 17, 2015 at 20:33

1 Answer 1


The only interesting quantity of a picture -- from a complexity perspective -- is the number of pixels, not its size.

Whether any given paper follows this observation is of course a different matter, but if nothing different is specified, I would assume that $N$ is the number of pixels indeed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.