Entropy conservation for comparison-based algorithms

DOI10.1016/j.topol.2021.107913MaRDI QIDQ2077296

Michel Schellekens

Publication date: 25 February 2022

Published in: Topology and its Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2011.07278

zbMATH Keywords

entropy; data structures; partial orders; linear extensions; sorting and searching; topological sorts; comparison-based algorithms; series-parallel partial orders

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

06A06: Partial orders, general

68P10: Searching and sorting

68Q55: Semantics in the theory of computing

94A17: Measures of information, entropy

68P05: Data structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Running time of the treapsort algorithm
• \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis
• Modeling concurrency with partial orders
• Counting linear extensions
• A characterization of partial metrizability: Domains are quantifiable.
• The correspondence between partial metrics and semivaluations
• The Analysis of Heapsort
• Non-Hausdorff Topology and Domain Theory
• Approximating SP-orders through total preorders: incomparability and transitivity through permutations
• Entropy and semivaluations on semilattices