[Solved]: Matrix Max in less than O(n)

Problem Detail: 

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.

Asked By : dobafresh

Answered By : G. Bach

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.

Best Answer from StackOverflow

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