# smallest-nonmember-problem

Given a finite set S of non-negative integers, the smallest-nonmember problem (Chapter 1) finds the smallest non-negative integer not in S. For example, { 0 1 3 } -> 2.

Here are three solutions, with successive solutions having asymptotically better worst-case behavior than the previous solutions.

``` (define (smallest-nsq s)

; Return the smallest non-negative integer not in s, a set
; of non-negative integers.

(let ((n (length s)))
(let loop ((i 0))
(if (and (< i n) (member i s))
(loop (+ i 1))
i))))

(define (smallest-nlogn s)

; Return the smallest non-negative integer not in s, a set
; of non-negative integers.

(let ((s (sort s <)))
(let loop ((smallest 0) (s s))
(if (null? s)
smallest
(let ((i (car s)))
(if (= smallest i)
(loop (+ smallest 1) (cdr s))
smallest))))))

(define (smallest-linear s)

; Return the smallest non-negative integer not in s, a set
; of non-negative integers.

(let* ((n (length s))
(found (make-vector (+ n 1) #f)))

(let loop ((s s))
(unless (null? s)
(let ((i (car s)))
(when (<= i n)
(vector-set! found i #t))
(loop (cdr s)))))

(let loop ((i 0))
(if (vector-ref found i)
(loop (+ i 1))
i))))
```

Caveats: smallest-nsq may not have O(n^2) worst-case behavior if member doesn't have linear behavior (e.g., it's implemented using a hash table, which seems unlikely). smallest-nlogn may not have O(n log n) worst-case behavior if sort doesn't have O(n log n) worst-case behavior (e.g., is insertion sort, or quicksort with unintelligent pivot selection on ordered data).