SICP Exercise 2.61

Question

Give an implementation of adjoin-set using the ordered representation. By analogy with element-of-set? show how to take advantage of the ordering to produce a procedure that requires on the average about half as many steps as with the unordered representation.

Answer

If x is smaller than the first element of set, we can simply cons them together. Otherwise, we cons together the first element of the set and adjoin-set of x to the cdr of the set. At some point, x will be smaller than the first element, and the function will return. If that never happens, we know x must be bigger than the largest element in set, so we append it to the end of the list.

(define (adjoin-set x set)
  (cond ((null? set) (append set (list x)))
        ((< x (car set)) (cons x set))
        (else (cons
               (car set)
               (adjoin-set x (cdr set))))))

Note that this still has a complexity of \(\Theta(n)\).