05/01/1992 09:00 AM
Computer Science
We study sorting and searching using a comparison oracle that ``lies.\'\' First, we prove that an algorithm of Rivest, Meyer, Kleitman, Winklmann and Spencer for searching in an n- element list using a comparison oracle that lies E times requires at most O(log n + E) comparisons, improving the best previously known bound of log n + E log log n + O(E log E). A lower bound, easily obtained from their results, establishes that the number of comparisons used by their algorithm is within a constant factor of optimal. We apply their search algorithm to obtain an algorithm for sorting an n element list with E lies that requires at most O(n log n + En) comparisons, improving on the algorithm of Lakshmanan, Ravikumar and Ganesan, which required at most O(n log n + En + E^2) comparisons. A lower bound proved by Lakshmanan, Ravikumar and Ganesan establishes that the number of comparisons used by our sorting algorithm is optimal to within a constant factor.
