diff options
Diffstat (limited to 'coding-exercises/2/59.rkt')
| -rw-r--r-- | coding-exercises/2/59.rkt | 5 |
1 files changed, 5 insertions, 0 deletions
diff --git a/coding-exercises/2/59.rkt b/coding-exercises/2/59.rkt index e5f3289..b9193bd 100644 --- a/coding-exercises/2/59.rkt +++ b/coding-exercises/2/59.rkt @@ -1,15 +1,19 @@ #lang racket ;; unordered distinct list + +;; linear scan of the elements O(n) (define (element-of-set? x myset) (cond ((null? myset) false) ((equal? x (car myset)) true) (else (element-of-set? x (cdr myset))))) +;; O(n) (define (adjoin-set x myset) (if (element-of-set? x myset) myset (cons x myset))) +;; linear scan of set1 and at each step we scan set2, O(n**2) (define (intersection-set set1 set2) (cond ((or (null? set1) (null? set2)) '()) ((element-of-set? (car set1) set2) @@ -18,6 +22,7 @@ (else (intersection-set (cdr set1) set2)))) (intersection-set (list 1 2 3) (list 'a 2 'c)) +;; linear scan of set1 and at each step we scan set2, O(n**2) (define (union-set set1 set2) (cond ((null? set1) set2) ((null? set2) set1) |