in O(n) time: Find greatest element in set where comparison is not transitive
The standard algorithm for finding a maximum still works. Start with $a_1$ and go over the elements, if you see a larger value, update the maximum to be that value. The reason this works is that every element you skipped is smaller than at least one element, and can thus not be the maximum.

To be clear, by the "standard algorithm" I mean the following:

max &lt;- a_1
for i=2 to n
   if a_i &gt; max
      max &lt;- a_i
output max


For completeness, I will discuss here the issues raised in the comments. The setting in the above discussion is finding a maximum relative to an anti symmetric relation $&lt;$, where $a_i$ is a maximum if for all $j\neq i$ we have $a_i&gt;a_j$. The above algorithm works under the assumption that a maximum exists, however if this is not known, one can use it to verify the existence of a maximum (check whether the returned element is indeed greater than all other elements, this is mentioned in Chi's comment and in Ilmari Karonen answer).

If $&lt;$ is not necessarily anti symmetric, then the above algorithm fails (as Emil mentioned in the comments). If $&lt;$ is an arbitrary relation (i.e. we are relaxing both transitivity and anti symmetry), then it is not hard to show that finding a maximum in linear time is not possible. Denote by $\#a_i$ the number of times $a_i$ participated in a query, we define an adversarial relation in a way that the maximum cannot be revealed without enough queries. Given the query $a_i &gt;?a_j $, answer $a_i&gt;a_j$ if $\# a_i &lt; n-1$ and $a_i&lt;a_j$ otherwise. If the number of queries is $o(n^2)$, then a maximum was not yet seen, and it can be set to be either of the elements in the set.