Is reading / writing a pixel slower than simple CPU operations (like addition)?

asked 2018-09-16 14:50:54 -0600

DanyAlejandro gravatar image

updated 2018-09-16 14:52:56 -0600

I'm trying to do complexity analysis on an algorithm that only has a couple of nested loops.

Traditional rule of thumb would be considering this a O(n*n) case (n number of pixels), but if I consider that reading and writing single pixel values is a more expensive operation than simple addition and subtraction of integers, the algorithm becomes O(n) for the number of non-empty pixels.

Is reading / writing a single pixel a much more complex operation than simple CPU-optimised operations like addition, subtraction, comparisons and assignment?

(Appending the algorithm in case someone needs specific details) image description

edit retag flag offensive close merge delete