[Solved]: What is the best complexity of finding a minimum in a matrix?

Problem Detail: 

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, jmin 

The 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?

Asked By : Jika

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44740

3.2K people like this

 Download Related Notes/Documents