The spread of a partial order

The deficiency of a partial order is the number of incomparable pairs. Another measure, the spread of a partial order is defined and its relation to the deficiency is established. In certain cases which arise naturally in the analysis of various sorting and selection algorithms where the partial order is only implicitly defined, the spread of the partial order is easier to estimate directly and provides a convenient way to estimate the deficiency.Partially supported by NSF Grant DCR-85-05053.Partially supported by NSF Grant DMS-85-05004.