Code

#lang racket

; unordered set with duplicates

(define (element-of-set? x set)
(cond ((null? set) false)
((equal? x (car set)) true)
(else (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
(cons x set))

(define (intersection-set set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((element-of-set? (car set1) set2)
(cons (car set1)
(intersection-set (cdr set1) set2)))
(else (intersection-set (cdr set1) set2))))

(define (union-set set1 set2)
(if (null? set1)
set2
(union-set (cdr set1) (cons (car set1) set2))))

; tests

(define set1 '(1 2 3 4))
(define set2 '(3 4 5 6))
(intersection-set set1 set2)
(union-set set1 set2)


Output

'(3 4)
'(4 3 2 1 3 4 5 6)


Set representation with no duplicates:

element-of-set?

• time ~ $$O(n)$$

adjoin-set

• time ~ $$O(n)$$

intersection-set

• time ~ $$O(n^2)$$

union-set

• time ~ $$O(n^2)$$

Set representation with duplicates:

element-of-set?

• time ~ $$O(n)$$
• slower on average when the set doesn't contain the element
• faster on average when the set contains the element

adjoin-set

• time ~ $$O(1)$$
• the sets require more memory

intersection-set

• time ~ $$O(n^2)$$
• slower on average because there are more elements to check

union-set

• time ~ $$O(n)$$

Sets with duplicates are useful when fast adjoins and unions are important.