What is the time-complexity of histogram computation?

Suppose I have an Image $I$ of $n\times m$ (or a matrix), I would like to compute its histograms in a loop.

Pseudocode:

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 ?

• Extra details of hist() function should be provided. Is I(i:i+s1, m) a function? The syntax isn't clear for me? – Mohamed Ennahdi El Idrissi Jul 19 '15 at 15:08
• $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 the other hand. – user35624 Jul 19 '15 at 15:12
• @MohamedEnnahdiElIdrissi I updated my question ... – user35624 Jul 19 '15 at 15:17

Presumably the time complexity of the function hist applied to data of length $N$ and to $B$ bins is $O(N+B)$ (the exact definition of $B$ depends on the implementation of hist; in your case, it seems to be the maximum of the input). In your case, each of the $n/s_1$ iterations of the loop is applied to data of length $s_1 m$, and so the total running time is $$\frac{n}{s_1} O(s_1m + B) = O(nm + \frac{n}{s_1} B).$$ The answer that your teacher expects is $O(nm)$.

• I don't have a teacher .... – user35624 Jul 19 '15 at 16:20
• but thank you for your answer :) – user35624 Jul 19 '15 at 16:20
• Well this is strange, following the analysis of this article ncbi.nlm.nih.gov/pubmed/21719256 it is supposed to be $O(h)$ with $h$ the height of the matrix/image. There is a problem – user35624 Jul 19 '15 at 16:25
• It's probably some kind of misunderstanding, which is unfortunately hard to decipher since the paper isn't open to the public. – Yuval Filmus Jul 19 '15 at 16:27
• (the exact definition of B depends on the implementation of hist; in your case, it seems to be the maximum of the input). ---> it is a constant corresponding to the number of unique elements in an array, for example [0 ,2,5,9] the bins is equal 4 because there is 4 distinct elements in the array. – user35624 Jul 19 '15 at 16:37

I hope you're familiar with C/Java syntax.

So, if I understand your algorithm, it should be composed of 3 nested loops; the first inner loop depends on the former, and the deepest loop is independent.

for ( i = 1; i <= n - s1; i +=s1 ) {
for ( j = 1; j <= i + s1; j ++ ) {
for ( k = 1; k <= m; k ++ ) {
bins[I[j,k]] ++; // frequency counting, symbolized by 'c'
}
}
}


Based on the above:

$$\\ T(n, m) = \frac{1}{s_1} \sum_{i = 1}^{ n - s_1} \sum_{j = 1}^{ i + s_1} \sum_{k = 1}^{ m}c \\ T(n,m) = \frac{c}{s_1} \sum_{i = 1}^{ n - s_1} \sum_{j = 1}^{ i + s_1}m \\ T(n, m) = \frac{cm}{s_1} \sum_{i = 1}^{ n - s_1}(i + s_1) \\ T(n, m) = \frac{cm}{s_1} \left(\sum_{i = 1}^{ n - s_1}i + \sum_{i = 1}^{ n - s_1}s_1\right) \\ T(n, m) = \frac{cm}{s_1} \left(\frac{(n - s_1)(n - s_1 + 1)}{2} + s_1(n - s_1)\right) \\ T(n, m) = \frac{cm}{s_1} \left( \frac{n^2 + n - s_1^2 - s_1}{2} \right) \\ \text{The order of growth is } \Theta(mn^2). \\ \text{In other words, when } n = m \text{, we can affirm } \Theta(n^3) \rightarrow \text{ Cubic order of growth.} \\ \text{and when } n < m \rightarrow T(n, m) \in \Omega(n^3) \\ \text{and when } n > m \rightarrow T(n, m) \in \mathcal{O}(n^3)$$

• There is a mistake here: the first loop should have i += s_1 rather than i++. That leads to a running time of $O(nm)$. – Yuval Filmus Jul 19 '15 at 18:40
• Yes, it's a mistake at the level of the loops, not at the level of the formula. Please refer to Unit03.ppt that I sent to you, slide 9. – Mohamed Ennahdi El Idrissi Jul 19 '15 at 19:18
• There are in fact several mistakes at the level of the formula, as well as at the level of the code (the second loop should have j < i + s1 rather than j <= i + s1). If the code were correct and $n$ is divisible by $s_1$ then the number of times the inner statement is executed should be exactly $nm$. – Yuval Filmus Jul 19 '15 at 19:21
• My code is an improvisation. Besides, smaller than or smaller than or equal is trivial when it comes to determining the order of growth. – Mohamed Ennahdi El Idrissi Jul 19 '15 at 19:45
• So the Order of growth is either quadratic or linear to $n\times m$ not linear to $O(n) only$ , I started a discussion about the original algorithm here : cstheory.stackexchange.com/questions/32033/… – user35624 Jul 19 '15 at 23:00