From SICP:

Exercise 2.61

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.

(define (adjoin-set x set)
  (define (rec subset) 
    (cond ((null? subset) (list x))
          ((> x (car subset)) (cons (car subset) (rec (cdr subset))))
          (else (cons x subset))))
  (if (element-of-set? x set)
      (rec set)))

Can this be improved?


1 Answer 1


Calling element-of-set? from adjoin-set introduces unnecessary redundancy. One may incorporate this test within the adjoin-set function (in your case, rec should be the main body of your function, with an = test added):

(define (adjoin-set x set)
    ((null? set) (cons x set))
    ((= x (car set)) set)
    ((< x (car set)) (cons x set))
    (else (cons (car set) (adjoin-set x (cdr set))))))

This function performs fewer steps since it does not call element-of-set?. However, its complexity is still O(n), which is the same as your implementation's complexity, as well as the complexity of element-of-set?.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.