title: Possible Error with an item on the AP Computer Science Exam
body: <p>I took the AP Computer Science Exam this year, and one of the questions, number 16 for me, appeared to actually not have a completely correct answer (although it was clear which answer the AP people had intended as the correct answer).</p>
  
  <p>The Question was as follows:</p>
  
  <blockquote>
    <p>Which of the following cannot be implemented on an array sorted in descending order more efficiently than on an unsorted array? <p>
    A.) Searching for an element<p>
    B.) Finding the median<p>
    C.) Finding arithmetic mean<p>
    D.) Outputting in ascending order<p>
    E.) Finding the largest value<p></p>
  </blockquote>
  
  <p>While naively, one would put answer C, I am pretty certain that that answer is not completely correct.</p>
  
  <p>Take this example:
  I have an array containing 4503599627370496 double-precision floating point values, one of which is equal to 9007199254740993, and the rest of which are all .999999.  Depending on <em>where</em> exactly the big value is, the naive method of finding the mean (iterating through the elements, summing them up, divide total by count) will not yield the correct value unless (1) the larger elements are added to the sum later (i.e. the array is sorted), (2) we use a higher-precision value to keep track of the sum (i.e. we use more resources), or (3) we use some other method that also requires more resources.</p>
  
  <p>And if it takes more resources, then by definition it is less efficient.</p>
  
  <p>Also, although this is rather avoiding the point, is that if you don't restrict yourself to the standard model for computing stuff (for instance if we allow quantum computers), any one of them becomes just as efficient on an unsorted array as a sorted array.</p>
  
  <p>Is the exam question actually defective, or did I miss something here?</p>