# What is the maximum number of comparisons needed to define a total order

Given a set of values $X=\{x_1,x_2,…,x_m\}$. I want to construct an irreflexive, transitive total order relation $>$ by doing pairwise comparisons among the values of $X$.

From trail and error I got $m-1$ comparisons needed. For values less than $m-1$, I can find an extension of the partial order. Does $m-1$ is the maximum number of comparisons needed to define a total order over $m$ values?

• I think I found this question confusing because the language "define a total order" suggests that you're building an abstract partially ordered set by specifying "less than" relationship among elements. However, it also seems like you could be given a disordered set of naturally ordered values and wish to sort via an algorithm. Jan 12, 2014 at 23:25
• When you say comparisons, we have been taking it to be the act of comparing two elements trying to determine the total order. It sounds like for you it is the longest chain. If so, it is true that the longest chain is $m-1$ elements and when you find one you have a total order. So for your $x_1 \gt x_2 \gt x_3$ is two comparisons (though it implies also $x_1 \gt x_3$) but we have been focused on how many calls to the comparison routine it takes to build up that chain. Jan 13, 2014 at 2:01

No, you are trying to sort the elements. The best comparison sort algorithms are of order $n \log n$. For 3 elements, in the worst case you need a minimum of 3 comparisons. Of course, you could get lucky and do the right two first. Say you find $x_1 \gt x_2$. If your next comparison gives $x_1 \gt x_3$ or $x_2 \lt x_3$ you don't know the complete order.

• Maybe my intuition is different from the question But I am interested in the maximum number of comparisons $k$ such that we are sure regardless of the comparisons results so far there is no total order with $k+1$ comparisons. In your example, there is always a total order extend the partial order. Jan 13, 2014 at 1:31
• So intuitively the goal is to have as large as possible number of comparisons. We can have $m-1$ comparisons in particular those with $(i,i+1)$ indices in $X$. With $m$ comparisons, depending on the results, we might have $x_1>…>x_1$ or a valid total order. Jan 13, 2014 at 1:37

It seems to me like $m-1$ comparisons will be necessary and sufficient.

If you think about the Hasse diagram for a totally ordered poset, it's basically a vertical path graph. If it has $m$ nodes, then it must have $m-1$ edges, or comparisons. Any fewer and your Hasse diagram is disconnected, any more and you will end up with redundant comparisons.

• You need more than that. For $m=3$, you can't (always) do it with 2 comparisons. Jan 12, 2014 at 22:50
• @CalvinLin You are correct. It now seems as though it might be a triangular number of comparisons needed to guarantee that you've got a total order. Thanks! Jan 12, 2014 at 23:09
• No, it's actually of the order $n \log n$ like Ross mentioned. The exact number for each $n$ isn't known, though here is a list in OEIS. Jan 12, 2014 at 23:12
• @CalvinLin So, looking on OEIS, I must be doing something wrong here. If I'm interpreting this correctly, for 4 elements, I need at most 5 comparisons. Let's say I want a < b < c < d. I choose a < d, b < d, c < d, (that's 3), then b<d, b<c (2 more), finally c<d. Jan 12, 2014 at 23:15
• You have the wrong interpretation of the problem. You do not know what the results of the comparisons are. For example, with $m=3$, we first pick any 2, call them $a, b$. The comparison could tell us (WLOG) that $a<b$. Now, we compare $a$ and $c$. If the comparison was $c<a$, then we are done. But if the comparison was $a<c$, then we still need 1 more. Jan 13, 2014 at 0:05