I would like to rank three items: $\{s,t,r\}$. Clearly there are $n!$ possibilities, and for each possibility, ie: if I have $s < t < r$, then this implies: $s < t, s < r, t < r$. Over all there seems to be $n^2 n!$ comparisons to be made.
Now suppose I measure the likelihood of a ranking with:
$Pr[s < t < r] = Pr[ s < t ] Pr [s < r] Pr[t < r],$
where the equality sign comes from the independence assumption of the problem. So again our sample space has $n!$ samples then to find the most likely ordering I would need to check n! samples, which is prohibitively expensive.
So the question is is there an algorithm to compute this value with lower complexity?