Suppose I have an Image $I$ of $n\times m$ (or a matrix), I would like to compute its histograms in a loop.
for i=1:s1:n h = hist(I(i:i+s1,m),bins) end
$I$ is a matrix (or an image of data). When we say, $I(i:i+s1,m)$ we take the block of the matrix that starts in row from $i$ to $i+s1$ and have $m$ elements in columns.
hist is a function that counts the number of elements in its first parameters and store that number in its $bins$. For example : $hist([1,2 ,1 ,1 ,3],3)$ is equals to $[3, 1, 1]$ because there is three elements of $1$ and just one elements of $2$ and $3$. $hist$ computes the frequency of an element.
So if I understand well ... the time-complexity of this simple algorithm is $O(n/s1) * TC(hist)$.
With the $TC(hist)$ the time-complexity of histogram computation. Since $s1$ is constant. I can deduce that TC of the algorithm is $O(n)*TC(hist)$.
If we use a hash table of size $bins$, (it is a memory, so it won't impact the time complexity). We will have to browse the $s1\times m$ part of the image. So the $TC(hist)$ is equal $O(s1*m)$.
I don't know how to link $O(s1*m)$ to the $n$ and $m$. Is $TC(hist)$ linear following $m$ so equals $O(m) $ since $s1$ is a constant ?
please, check if my reasoning is correct ? and what is the global time-complexity ? do we take in consideration the memory usage in the computation of time-complexity ?