Following on some talk about the electoral college:

Say you have a set S of n elements, s(1)...s(n). There is some total ordering relation ~ defined on S, such that for any i,j between 1 and n you can always determine whether s(i)~s(j). By comparing elements of S two at a time, what is the minimum number of comparisons needed to arrange S in order according to ~?

In other words, say you're voting for candidates for a political office, chosen from n candidates. For any two candidates, you can definitely say I prefer A to B, but you can only look at candidates two at a time, and your preferences must be consistent (as per the total ordering), i.e. you can't say I prefer Alfred to Beatrice and I prefer Beatrice to Clarence and I prefer Clarence to Alfred. How many comparisons are necessary to put the n candidates in order of preference?

All right, I have a fast method, and I know about how many comparisons it takes given some n. I have a hunch that on average it is optimal. Can you tell me what it is?

Originally posted by royalchicken All right, I have a fast method, and I know about how many comparisons it takes given some n. I have a hunch that on average it is optimal. Can you tell me what it is?