The spread of a partial order (Q1099196)

Given a partially ordered set \(P=({\mathbb{P}},<_ P)\) the authors define the deficiency D(P) of a partial order as the number of incomparable pairs. Since it is not always straightforward to estimate D(P), they introduce an alternative way to estimate D(P), they introduce an alternative way to estimate D(P) by introducing another measure for P which they call the spread of P-S(P). In certain cases which arise naturally in the analysis of various sorting and selection algorithms where the patial order is only implicitly defined, the spread of the patial order is easier to estimate directly and provides a convenient way to estimate the deficiency. Then they give sharp bounds for the relationship between D(P) and S(P).