The most efficient way to find a minimal value in a 2 dimensional matrix.

Question

Suppose we have a matrix A with value of elements ranging from 0 to 255 ( a greyscale image). What is the most efficient algorithm that will return a minimal value found in this matrix?

Answer 1

If we can't suppose any correlation between the values of the matrix cells, we have to look, at least, once to each value, so it would be:

Input: matrix A of n,m rows,columns
min = 255
for i = 1..n
    for j = 1..m
        if A(i,j) < min: min = A(i,j)
        if min = 0: break loops

Output: minimum value: min

If correlation can be expected, for example, if there are no huge contrast changes in a small region, you could heuristcally eliminate regions in which you find big values together...

The above algorithm runs in $O(nm)$ in the worst case. (In exactly $nm$ steps in the worst case).