Assume two hash-indexed collections and exist and that collection from a previous state must be compared to collection from the current state. The task is to find an efficient method to:
For the exercise you are allowed to use only comparisons, set operations and not allowed to introduce intermediary variables.
(1) Given the two sets, initial set and new set , the intersect can obtained via and the result assigned to such that will contain only the elements common to both and . Since the exercise mentions hash-indexed collections, one can assume that and are proper mathematical sets with no duplicate elements, such that using a simple length comparison between and will reveal whether the sets are equal. (2) Finally, since now contains elements in both and , an union can be performed between and and assigned to which will yield a set that contains the elements of and any new elements in .
For the first point (1), the time complexity would be , the comparison is an operation such that the first point carries an overall complexity of . The second point (2) also requires time complexity.