On the Complexity of Partial Order Productions
Report ID: TR-136-88Author: Yao, Andrew
Date: 1988-02-00
Pages: 17
Download Formats: |PDF|
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.