The asymptotic complexity of partial sorting -- How to learn large posets by pairwise comparisons
<|reference_start|>The asymptotic complexity of partial sorting -- How to learn large posets by pairwise comparisons: The 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.<|reference_end|>
@article{heitzig2002the,
    title={The asymptotic complexity of partial sorting -- How to learn large
  posets by pairwise comparisons},
    author={Jobst Heitzig},
    journal={arXiv preprint arXiv:math/0205049},
    year={2002},
    archivePrefix={arXiv},
    eprint={math/0205049},
    primaryClass={math.CO cs.CC math.OC}
}