SICP Exercise 2.62

2023-01-30

Question

Give a \(\Theta(n)\) implementation of union-set for sets represented as ordered lists.

Answer

My first instinct was to use adjoin-set from the previous question for this:

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else (union-set (cdr set1)
			 (adjoin-set (car set1) set2)))))

While this is very nice, it is not \(\Theta(n)\). Since adjoin-set is itself \(\Theta(n)\) and we are calling it \(n\) times, we still have \(\Theta(n^2)\).

The following actually has \(\Theta(n)\):

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((= (car set1) (car set2))
         (cons (car set1) (union-set (cdr set1)
                                     (cdr set2))))
        ((< (car set1) (car set2))
         (cons (car set1) (union-set (cdr set1)
                                     set2)))
        ((> (car set1) (car set2))
         (cons (car set2) (union-set set1
                                     (cdr set2))))))

Let’s test it:

(define s1 '(1 3 5 9))
(define s2 '(4 5 6 7 8))
(union-set s1 s2)

Results:

(1 3 4 5 6 7 8 9)