Given a matrix $\mathsf{a}$ of size $K\times N$, what is the best complexity of finding the minimum value?Here is a pseudo code:function find_min(a)    imin, jmin = 1, 1    for k = 1 to K        for n = 1 to N            if a[k, n] < a[imin, jmin]                imin = k                    jmin = n    return imin, jminThe above function needs $O(K\cdot N)$ operations. However, I think we can reduce the complexity to $O(\lg K\cdot N)$ using a heap. Am I right? Can we do better than a heap? If so, what is the best complexity of such a function?
What is the best complexity of finding a minimum in a matrix?
algorithms;time complexity;asymptotics
You can't find the minimum without reading all values, due to an adversary argument. The adversary pretends that the matrix is the zero matrix, that is, whenever you ask for some value in the matrix, it answers zero. If you haven't queried some entry, then the algorithm cannot distinguish between two possibilities: that the matrix is entirely zero, or that it is zero apart from the entry, which has value 1. The minimum in both cases is different, so the algorithm can't be correct.