1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Related: What's the minimum time to read the input? What's the minimum time to insert the input into a heap (starting from an empty heap)? $\endgroup$ Jul 26, 2015 at 4:52

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.