11.6.1 An Input Validation

One final point involving time and storage trade-offs. Suppose an input validation must be added to topsort just prior to the processing of the current i, j pair read in phase I. The function is to check whether i, j is a duplicate of an earlier input pair. If so, it is to be ignored; if not, it is to be processed. One way to accomplish this, which requires no additional storage, is to traverse the current list of successors of object i. If j appears on the list as a successor, then i, j is a duplicate; otherwise it is not. This takes time proportional to the current number of successors of i and thus adds a total time to phase I that is proportional to m². Instead, the function can work in constant time if n(n - 1) additional storage is available. Use the storage for an n(n - 1) array that is initialized to all zeros. When i, j is read, simply test the (i, j)th array entry. If it is zero, the pair is not a duplicate. Then set the entry to 1 to indicate that this i, j pair has been processed. In this way, an entry of 1 will mean that the pair is a duplicate from now on. This adds total time to phase I of O(m) but requires n(n - 1) additional storage.