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).