Abstract :
It is very well known in computer science that partially ordered files are easier to search. In the worst case, for example, a totally unordered file requires no preprocessing, but ¿(n) time to search, while a totally ordered file requires ¿(n log n) preprocessing time to sort, but can be searched in O(log n) time. Behind the casual observation, then, lurks the notion of a computational tradeoff between sorting and searching. We analyze this tradeoff in the average case, using the decision tree model. Let P be a preprocessing algorithm that produces partial orders given a set U of n elements, and let S be a searching algorithm for these partial orders. Assuming any of the n! permutations of the elements of U are equally likely, and that we search for any y isin; U with equal probability (in unsuccessful search, all "gaps" are considered equally likely), the average costs P(n) of preprocessing and S(n) of searching may be computed. We demonstrate a tradeoff of the form P(n) + n log S(n) = ¿(n log n), for both successful and unsuccessful search. The bound is tight up to a constant factor. In proving this tradeoff, we show a lower bound on the average case of searching a partial order. Let A be a partial order on n elements consistent with Π permutations. We show S(n) = ¿(Π3/n/n2) for successful search of A, and S(n) = ¿(Π2/n/n) for unsuccessful search. These lower bounds show, for example, that heaps require linear time to search on the average.
