In the paper
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 ...