Time complexity of a vertical sweep algorithm with histogram computations

Question

In the paper

• Quick Detection of Brain Tumors and Edemas: A Bounding Box Method Using Symmetry, Saha et al

the authors claim that the running time of the algorithm (Matlab implementation) is $O(h)$. I don't understand how they arrive at this.

The algorithm works as follows: The algorithm does a vertical sweep of a whole image of size $h\times w$. For every $l$ between $0$ and $h$, a score function $s$ is computed. To compute $s$ we we calculate histogram computation of the four parts of the whole image : $[0:l,1:w/2]$, $[l:h,1:w/2]$, $[0:l,w/2:end]$ and $[l:end,w/2:end]$.

How do they arrive at $O(h)$ time complexity for the algorithm? Do they consider histogram computation to be $O(1)$?

PS: This question is related to What is the time-complexity of histogram computation? but I hope to get the exact answer in concrete case this time ...

Answer 1

$O(h)$ sounds hard to believe, unless there's some pre computation that's not counted here, as it takes $\Theta(hw)$ time just to read every pixel of the image.

Computing a histogram from scratch can't be done in $O(1)$ time. But updating a histogram can be done efficiently. If you already have a histogram for some set of pixels, and then you add or delete one pixel, you can update the histogram in $O(1)$ time. This kind of idea can be used to speed up the sort of thing you're talking about, because all of the histograms we want are closely related.

In particular, when we increment $l$, we add or delete a row from a histogram. Thus you can update the histogram more efficiently than computing it from scratch.