[racket] Looking for feedback on code style

The following measurement shows O(n).
But O(n) = O(C+n) where C may be a big number.
Jos

#lang racket

#|
(select k lor (randomize? #f)) -> r
k          : exact integer number.
lor        : non empty list of real numbers.
randomize? : if false lor is supposed to be in random order.
r          : real number, specifically an element of [lor].
condition  : (<= 0 k (sub1 (length lor))).
purpose    : r = (list-ref (sort lor <) k).
method     : [lor] is partially sorted by partitioning as in quicksort,
             but recurring on one of the patitions only.
|#

(define (select k lor (randomize? #f))
  (unless (and (list? lor) (andmap real? lor) (pair? lor))
    (raise-type-error 'select "non empty list of reals" 1 k lor))
  (let ((n (length lor)))
    (unless (and (exact-integer? k) (<= 0 k (sub1 n)))
      (raise-type-error 'select "exact integer (<= 0 k (length lor)" 0 k
lor))
    (select-aux k lor n randomize?)))

(define (select-aux k lor n (randomize? #f))
  (let*-values
      (((r) (list-ref lor (if randomize? (random n) 0)))
       ((nlt neq ngt lt gt) (partition lor r)))
    (cond
      ((< k nlt) (select-aux k lt nlt randomize?))
      ((< k (+ nlt neq)) r)
      (else (select-aux (- k nlt neq) gt ngt randomize?)))))


#|
(partition r lor (randomize? #f)) -> nlt neq ngt lt gt
lor        : non empty list of real
r          : one of the elements of [lor].
randomize? : if false [lor] is supposed to be in random order.
nlt        : number of elements of lor less than [r].
neq        : number of elements of lor equal to [r].
ngt        : number of elements of lor greater than [r].
lt         : list of elements of lor less than [r].
gt         : list of elements of lor greater than [r].
|#

(define (partition lor r)
  (partition-aux lor r 0 0 0 '() `()))

(define (partition-aux lor r nlt neq ngt lt gt)
  (if (null? lor) (values nlt neq ngt lt gt)
      (let ((e (car lor)))
        (cond
          ((< e r)
           (partition-aux (cdr lor) r
                          (add1 nlt) neq ngt
                          (cons e lt) gt))
          ((> e r)
           (partition-aux (cdr lor) r
                          nlt neq (add1 ngt)
                          lt (cons e gt)))
          (else
           (partition-aux (cdr lor) r
                          nlt (add1 neq) ngt
                          lt gt))))))

; Timing O(n), where n is the length of lor.

; Measure times for [n] (inrange start fin step).
; For each  [n] take a mean of  [repeaqt] measurements.

(define (timer start step fin repeat)
  (print-header)
  (random 1)
  (for ((n (in-range start fin step)))
    (let loop ((cpu-time 0) (cpu-gc-time 0) (i repeat))
      (if (zero? i) (print-results n cpu-time cpu-gc-time repeat)
          (let*-values
              (((k) (random n))
               ((lor) (build-list n (lambda (ignore) (random n))))
               ((cpu cpu-gc) (times (select k lor))))
            (loop (+ cpu-time cpu) (+ cpu-gc cpu-gc-time) (sub1 i)))))))

(define (print-header)
  (printf
   "lenth of lor, cpu time, cpu-gc~n~
    times are in nanoseconds.~n~
    they show mean time of one select call divided by the length of
lor.~n"))

(define (print-results n cpu cpu-gc repeat)
  (printf "~s ~a ~a~n" n
          (real->decimal-string (/ (* 1000 cpu   ) (* n repeat)) 6)
          (real->decimal-string (/ (* 1000 cpu-gc) (* n repeat)) 6)))

(define-syntax times
  (syntax-rules ()
    ((timer expr)
     (let ((port (open-output-string)))
       (parameterize ((current-output-port port))
         (time expr))
       ;(display (get-output-string port))
       (let ((port (open-input-string (get-output-string port))))
         (parameterize ((current-input-port port))
           (let ((cpu  (begin (read) (read) (read)))
                 (real (begin (read) (read) (read)))
                 (gc   (begin (read) (read) (read))))
             (values cpu (- cpu gc)))))))))

(timer 100000 100000 1000000 100)

> -----Original Message-----
> From: users-bounces at racket-lang.org 
> [mailto:users-bounces at racket-lang.org] On Behalf Of Stephen Bloch
> Sent: 13 September 2010 21:44
> To: users at racket-lang.org
> Subject: Re: [racket] Looking for feedback on code style
> 
> 
> On Sep 13, 2010, at 3:07 PM, David Van Horn wrote:
> 
> >> In fact, ANY method to do this (even with a vector) takes 
> Omega(n log 
> >> n) time. It needs to be able to produce any of n! 
> different answers, 
> >> so it needs to make at least log(n!) decisions, which is 
> Theta(n log n).
> >> Otherwise there wouldn't be enough leaves on the decision tree.
> > 
> > Doesn't it make n decisions?  1 decision for each element 
> (the decision being, where does the element go in the shuffled list)?
> 
> Each of these is an n-way decision, which takes log(n) bits 
> to specify.  Any algorithm that solves this problem MUST 
> generate at least n log(n) random bits of information, and 
> therefore MUST take at least n log(n) time (ignoring parallelism).
> 
> Ryan Culpeper points out:
> > I think the discrepancy comes from the fact that each of 
> those decisions takes O(log n) bits, but we customarily 
> pretend that "indexes" are O(1).
> 
> Exactly.  As long as your n fits into a machine word, and you 
> have at least n cells of truly-random-access memory, you can 
> treat array indexing and random-number-generation as taking O(1) time.
> 
> > Is this right? Does complexity analysis have a notation for 
> distinguishing "true" complexity from "for up to k bits" complexity?
> 
> Not exactly a "notation" AFAIK, but people do routinely talk 
> about whether the computational model allows bit operations 
> in O(1) time, or integer operations in O(1) time, or whatever.
> 
> 
> Stephen Bloch
> sbloch at adelphi.edu
> 
> _________________________________________________
>   For list-related administrative tasks:
>   http://lists.racket-lang.org/listinfo/users