A note on the expected time for finding maxima by list algorithms

Maxima in R-d are found incrementally by maintaining a linked list and comp aring new elements against the linked list. If the elements are independent and uniformly distributed in the unit square [0, 1](d), then, regardless o f how the list is manipulated by an adversary, the expected time is O(n log (d-2) n). This should be contrasted with the fact that the expected number of maxims grows as log(d-1) n, so no adversary can force an expected comple xity of n log(d-1) n. Note that the expected complexity is O(n) for d = 2. Conversely, there are list-manipulating adversaries for which the given bou nd is attained. However, if we naively add maxima to the list without chang ing the order. then the expected number of element comparisons is n + o(n) for any d greater than or equal to 2. In the paper we also derive new tail bounds and moment inequalities for the number of maxima.