Aha!  I understood.  I looked at select.scm and saw %%vector-select recursed and

blindly assumed input length * recurse depth complexity, but in every iteration

the expected length shrinks in geometric series, so the sum is constant multiples

of input size.

Thanks for enlightenment.

On Tue, Jan 24, 2017 at 5:10 PM, Alex Shinn <xxxxxx@gmail.com> wrote:

On Wed, Jan 25, 2017 at 11:23 AM, Shiro Kawai <xxxxxx@gmail.com> wrote:

Yes, vector-select is O(n + k ln k), so if k is fixed, it's O(n).  However, in median case k = n/2 and you can't fix k, can you?

vector-select is O(n), independent of k, as using the

algorithm I provided in selection.scm.  See

https://en.wikipedia.org/wiki/Selection_algorithm.

A simple (untested) linear version of vector-find-median is then:

(define (vector-find-median < v knil . o)

  (let ((len (vector-length v)))

    (cond

     ((zero? len) knil)

     ((odd? len) (vector-select! < (vector-copy v) (+ 1 (quotient len 2))))

     (else

      (let ((mid (quotient len 2))

             (v (vector-copy v))

             (mean (if (pair? o) (car o) (lambda (a b) (/ (+ a b) 2)))))

        (mean (vector-select! < v mid) (vector-select! < v (+ mid 1))))))))

-- 

Alex