SICP Exercise 2.60

Question

We specified that a set would be represented as a list with no duplicates. Now suppose we allow duplicates. For instance, the set $\{1,2,3\}$ could be represented as the list (2 3 2 1 3 2 2). Design procedures element-of-set?, adjoin-set, union-set, and intersection-set that operate on this representation. How does the efficiency of each compare with the corresponding procedure for the non-duplicate representation? Are there applications for which you would use this representation in preference to the non-duplicate one?

Answer

The only functions which actually need to change here are adjoin-set and union-set, since we no longer need to check the entire set for matches from the original set. The new functions looks like this:

copy(define (adjoin-set x set) (cons x set))

(define (union-set set1 set2) (append set1 set2))

This is a much simpler operation which will need less computing resources than our previous implementation.

Our new adjoin-set is just a wrapper for cons and as such will have a complexity of $\mathrm{\Theta }(1)$.

The new union-set now only needs to cons each element from one set to the other, giving it a reduced complexity of $\mathrm{\Theta }(n)$.