DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE                
                               ODENSE UNIVERSITY                               

                       Randomized Analytic Decision Trees                      

                                 Michael Ben-Or                                
                           Computer Science Institute                          
                             The Hebrew University                             

                     Tuesday, September 5, 1995, at 2:15 PM                    
                                The Seminar Room                               


  How many comparisons  are needed to  find the maximum,  or the median,  of n
  real numbers, if  we allow  randomization, and the  free computation  of any
  analytic  real  function  of  the  inputs.  Rabin  (1972)  proved  that  n-1
  comparisons are needed to verify  that a given element is  the maximum if no
  error is allowed, and  Ting and Yao  (1994) gave a  randomized algorithm for
  finding the maximum  with O(log^2  n) expected  number of  comparisons if  a
  small error probability is allowed. We present a new simple proof of Rabin's
  result and extend this  to show that for  all k<n-1, at  least k comparisons
  are needed  to verify  that a  given element  is  the maximum  if the  error
  probability is less than  1/2^k.  We further show  that Omega(n) comparisons
  are needed to verify that a given element is the median of n real numbers if
  the error probability is O(1/n^(3/2)).


                                                                 Joan F. Boyar