moar

1 files changed, 7 insertions, 3 deletions

diff --git a/coding-exercises/2/60.rkt b/coding-exercises/2/60.rkt
index 3effe1c..fba2086 100644
--- a/coding-exercises/2/60.rkt
+++ b/coding-exercises/2/60.rkt
@@ -1,20 +1,24 @@
 #lang racket
 ;; unordered duplicates list
-;; can be use if adjoin needs to be fast O(1)
-;; append is linear so union is O(n)
-;; Tried to make intersection better for case with lot of duplicates and large n
+
+;; linear scan of 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)))))
 
+;; can be use if adjoin needs to be fast O(1)
 (define (adjoin-set x myset)
   (cons x myset))
 
+;; append is linear so union is O(n)
 (define (union-set set1 set2)
   (append set1 set2))
 (union-set (list 1 1 1 1 1 1 1 2 3) (list 2 2 2 2 2 3 'c))
 
+;; Tried to make intersection better for case with lot of duplicates and large n by short circuiting before the linear scan overhead
+;; , but it will still have O(n**2) worst case performance
+;; not sure about average case
 (define (intersection-set set1 set2)
   (define (iter s1 s2 result)
     (cond ((or (null? s1) (null? s2)) result)