|
TR-136-88
On the Complexity of Partial Order Productions |
|
| Authors: | Yao, Andrew Chi-Chih |
| Date: | February 1988 |
| Pages: | 17 |
| Download Formats: | [PDF] |
(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. |
|