As Ariel notes, the standard maximum-finding algorithm given below:
def find_maximum(a):
m = a[0]
for x in a:
if x > m: m = x
return m
will in fact work without modification as long as:
- any pair of elements can be compared, and
- the input is guaranteed to contain a maximal element, i.e. an element that is pairwise greater than any other element in the input.
(The first assumption above can actually be relaxed, even without having to modify the algorithm, as long as we assume that the maximal element is comparable with every other element and that x > y
is always false if the elements x
and y
are incomparable.)
In particular, your claim that:
[…] to be certain of an answer, the element needs to be explicitly compared to every other element (because comparison is not transitive).
is not true under the assumptions given above. In fact, to prove that the algorithm above will always find the maximal element, it's sufficient to observe that:
- since the loop iterates over all the input elements, at some iteration
x
will be the maximal element;
- since the maximal element is pairwise greater than every other element, it follows that, at the end of that iteration,
m
will be the maximal element; and
- since no other element can be pairwise greater than the maximal element, it follows that
m
will not change on any of the subsequent iterations.
Therefore, at the end of the loop, m
will always be the maximal element, if the input contains one.
Ps. If the input does not necessarily always contain a maximal element, then verifying that fact will indeed require testing the candidate answer against every other element to verify that it is really maximal. However, we can still do that in O(n) time after running the maximum-finding algorithm above:
def find_maximum_if_any(a):
# step 1: find the maximum, if one exists
m = a[0]
for x in a:
if x > m: m = x
# step 2: verify that the element we found is indeed maximal
for x in a:
if x > m: return None # the input contains no maximal element
return m # yes, m is a maximal element
(I'm assuming here that the relation >
is irreflexive, i.e. no element can be greater than itself. If that's not necessarily the case, the comparison x > m
in step 2 should be replaced with x ≠ m and x > m
, where ≠
denotes identity comparison. Or we could just apply the optimization noted below.)
To prove the correctness of this variation of the algorithm, consider the two possible cases:
- If the input contains a maximal element, then step 1 will find it (as shown above) and step 2 will confirm it.
- If the input does not contain a maximal element, then step 1 will end up picking some arbitrary element as
m
. It doesn't matter which element it is, since it will in any case be non-maximal, and therefore step 2 will detect that and return None
.
If we stored the index of m
in the input array a
, we could actually optimize step 2 to only check those elements that come before m
in a
, since any later elements have already been compared with m
in step 1. But this optimization does not change the asymptotic time complexity of the algorithm, which is still O(n).