Matrix Max in less than O(n)

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.

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.

StackExchange Computer Science Q#50186, answer score: 15