The asymptotic complexity of partial sorting -- How to learn large posets by pairwise comparisons

2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/63984The expected number of pairwise comparisons needed to learn a partial order on n elements is shown to be at least n*n/4-o(n*n), and an algorithm is given that needs only n*n/4+o(n*n) comparisons on average. In addition, the optimal strategy for learning a poset with four elements is presented.CombinatoricsComputational ComplexityOptimization and Control06A07; 11Y16The asymptotic complexity of partial sorting -- How to learn large posets by pairwise comparisonstext