SICP Exercise 2.62

2023-01-30

Question

Give a $Θ (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 $Θ (n)$ . Since adjoin-set is itself $Θ (n)$ and we are calling it $n$ times, we still have $Θ (n^{2})$ .

The following actually has $Θ (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)