4
$\begingroup$

I am attempting to find the maximum value in a matrix (or 2d array) and want to find it in less than O(n) time. The easiest way, which results in O(n) run time, is an element wise search. If a better run time is possible, I would also like to find any values over a specific threshold in less than O(n) time. Is any of this possible?

I cannot re-sort and do a binary search or something along those lines as the ordering is important.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ If you can't sort or if you don't have any information on the organization of the data, you cannot do better than O(n). $\endgroup$ – ryuu9187 Dec 1 '15 at 19:34
  • 1
    $\begingroup$ consider this problem at its simplest. You have value A = randomly 4 (fair dice roll). You want to know if value B is bigger. You have no information on value B. Can you figure that out without looking at value B? $\endgroup$ – njzk2 Dec 1 '15 at 20:53
15
$\begingroup$

If you don't know anything about the contents of the matrix (such as some kind of monotonicity property), linear time is the best you can do for a one-off search with a deterministic algorithm by a simple adversary argument: if you don't look at everything, then you can't distinguish between the cases where the maximum component is/isn't one of the ones you didn't look at. If you want to maintain max-information for a dynamic matrix, then there might be suitable preprocessing and maintenance (for example, a search tree) that can speed things up.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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