BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-73-349
       ENTRY:: September 25, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Two papers on the selection problem: Time Bounds for
               Selection [by Manual Blum, Robert W. Floyd, Vaughan Pratt,
               Ronald L. Rivest, and Robert E. Tarjan] and Expected Time
               Bounds for Selection [by Robert W. Floyd and Ronald L.
               Rivest].
        TYPE:: Technical Report
      AUTHOR:: Blum, Manual
      AUTHOR:: Floyd, Robert W.
      AUTHOR:: Pratt, Vaughan R.
      AUTHOR:: Rivest, Ronald L.
      AUTHOR:: Tarjan, Robert Endre
        DATE:: April 1973
       PAGES:: 53
    ABSTRACT:: (1) The number of comparisons required to select the i-th
               smallest of n numbers is shown to be at most a linear
               function of n by analysis of a new selection algorithm --
               PICK. Specifically, no more than 5.4305 n comparisons are
               ever required. This bound is improved for extreme values of
               i, and a new lower bound on the requisite number of
               comparisons is also proved.

               (2) A new selection algorithm is presented which is shown to
               be very efficient on the average, both theoretically and
               practically. The number of comparisons used to select the
               i-th smallest of n numbers is n + min(i,n-i) + o(n). A lower
               bound within 9% of the above formula is also derived.
       NOTES:: [Adminitrivia V1/Prg/19950925]
         END:: STAN//CS-TR-73-349