On the Complexity of Partial Order Productions

Abstract:

(abbreviated abstract) Sorting and median-finding of a set of n numbers are two of the classical problems in combinatorial computation. In both problems, the worst-case complexity and the average-case complexity are of the same order of magnitude. Are they special cases of a general class of problems for which this problem is true? In this paper we will show that this is indeed so.