2026-07-23T08:35:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19380 2024-03-06T11:03:53Z ddc:004 open_access

An Optimal Algorithm for Sorting in Trees Roychoudhury, Jishnu Yadav, Jatin Sorting Trees Sorting is a foundational problem in computer science that is typically employed on sequences or total orders. More recently, a more general form of sorting on partially ordered sets (or posets), where some pairs of elements are incomparable, has been studied. General poset sorting algorithms have a lower-bound query complexity of Ω(wn + n log n), where w is the width of the poset. We consider the problem of sorting in trees, a particular case of partial orders. This problem is equivalent to the problem of reconstructing a rooted directed tree from path queries. We parametrize the complexity with respect to d, the maximum degree of an element in the tree, as d is usually much smaller than w in trees. For example, in complete binary trees, d = Θ(1), w = Θ(n). The previous known upper bounds are O(dn log² n) [Wang and Honorio, 2019] and O(d² n log n) [Ramtin Afshar et al., 2020], and a recent paper proves a lower bound of Ω(dn log_d n) [Paul Bastide, 2023] for any Las Vegas randomized algorithm. In this paper, we settle the complexity of the problem by presenting a randomized algorithm with worst-case expected O(dnlog_d n) query and time complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jishnu Roychoudhury and Jatin Yadav 2023 Is Part Of LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2023.7 urn:nbn:de:0030-drops-193807 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.7 eng https://creativecommons.org/licenses/by/4.0/legalcode