Sort With a 90%-Accurate Paid Comparator: Algorithm, Accuracy and Cost

You are given a set of `n` objects that must be sorted by an underlying value you cannot read directly. The only way to learn anything about the values is a paid comparison API: given two objects, it reports which of the two has the greater value. Each answer is correct with probability 0.9 and wrong with probability 0.1, and every call costs 1 cent. Design a sorting algorithm that uses this API, and compute both the accuracy of the order it returns and the cost of producing it. ### Constraints and Clarifications - The API is the only source of information about the values. Rearranging objects is free; only API calls cost money. - `n` is not fixed, so express accuracy and cost as functions of `n` and of any parameter your design introduces, then evaluate them for a small concrete `n`. - Assume every object has a distinct value, so exactly one order is correct. ### Clarifying Questions - Are the API's errors independent from call to call, including when the same pair is asked again, or does a given pair always receive the same, possibly wrong, answer? - What does "accuracy" mean here: the probability that the entire order is exactly right, or a softer measure such as the number of pairs left out of order? - Is there a budget to stay within, or a target accuracy to reach at the lowest cost? - Is the 90% figure the same for every pair, or are pairs with close values harder to compare? ### Part 1 — One call per comparison Take a standard comparison sort and call the API once whenever the algorithm needs a comparison. How many calls does it make, what does it cost, and what is the probability that its output is exactly the correct order? How does that probability behave as `n` grows? ```hint Which errors are fatal Pick your algorithm, then ask whether a single wrong answer can ever be corrected later in that algorithm, or whether it always survives into the output. ``` #### What This Part Should Cover - The number of comparisons the chosen algorithm makes, in the worst case or typically, and the resulting cost in cents - The probability of an exactly correct output, and why it collapses as `n` grows - Why the choice of algorithm matters when every comparison is both paid and fallible ### Part 2 — Spend more calls to buy accuracy A single answer is wrong 10% of the time. Change the design so that the final order is much more likely to be correct. Give its accuracy and its cost as functions of `n` and of the parameter you tune, and explain how you would set that parameter to reach a target overall accuracy at the lowest cost. ```hint Asking again If errors are independent, consider what several answers to the same question tell you together, and how quickly their combined error shrinks as you ask more often. ``` #### What This Part Should Cover - The error of one improved comparison, computed exactly or bounded - How the per-comparison errors combine into the accuracy of the whole sort - Total cost as a function of `n` and of the target accuracy, and how it scales - At least one way to reach the same accuracy with fewer calls ### What a Strong Answer Covers - An explicit noise model and accuracy definition, stated before any numbers - Correct probability arithmetic for combined answers and for the whole sort, checked on a small concrete `n` - Accuracy and cost presented as a trade-off curve over the tuning parameter, not as a single number - Awareness that a comparator giving inconsistent answers can break or mislead standard sort implementations - What changes in the design if the errors are not independent ### Follow-up Questions - If the same pair always gets the same answer, so asking again does not help, what is the best you can do, and at what cost? - If accuracy means few out-of-order pairs rather than an exactly correct order, which algorithm would you choose, and why? - If you only need the single greatest object, or the top few, how do the accuracy and cost change?