Chapter 2, Building Abstractions with Data

Section - 2.3 Symbolic Data

Exercise 2.61


1
2
3
4
5
6
7
(define (adjoin-set x set)
  (cond ((null? set) (cons x set))
        ((< x (car set)) (cons x set))
        ((= x (car set)) set)        
        (else (cons (car set) (adjoin-set x (cdr set))))
  )
)

Test/Output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> (display (adjoin-set 5 '(1 2 3 6 9)))
(1 2 3 5 6 9)
> (display (adjoin-set 0 '(1 2 3 6 9)))
(0 1 2 3 6 9)
> (display (adjoin-set 10 '(1 2 3 6 9)))
(1 2 3 6 9 10)
> (display (adjoin-set 1 '(1 2 3 6 9)))
(1 2 3 6 9)
> (display (adjoin-set 9 '(1 2 3 6 9)))
(1 2 3 6 9)
> (display (adjoin-set 6 '(1 2 3 6 9)))
(1 2 3 6 9)
> (display (adjoin-set 15 '(1 2 3 6 9)))
(1 2 3 6 9 15)
> 

Sometimes, adding an element chances are that we only need to add the new element in the front of the list, thus in $\theta(1)$.

Sometimes, adding an element chances are that we need to add the new element in the end of the list, thus in $\theta(n)$.

Thus on average we have the complexity of $\theta( \frac n 2 )$.