Fragile complexity of adaptive algorithms

Prosenjit Bose, Pilar Cano*, Rolf Fagerberg, John Iacono, Riko Jacob, Stefan Langerman

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstract

The fragile complexity of a comparison-based algorithm is f(n) if each input element participates in O(f(n)) comparisons. In this paper, we explore the fragile complexity of algorithms adaptive to various restrictions on the input, i.e., algorithms with a fragile complexity parameterized by a quantity other than the input size n. We show that searching for the predecessor in a sorted array has fragile complexity Θ(log⁡k), where k is the rank of the query element, both in a randomized and a deterministic setting. For predecessor searches, we also show how to optimally reduce the amortized fragile complexity of the elements in the array. We also prove the following results: Selecting the kth smallest element has expected fragile complexity O(log⁡log⁡k) for the element selected. Deterministically finding the minimum element has fragile complexity Θ(log⁡(Inv)) and Θ(log⁡(Runs)), where Inv is the number of inversions in a sequence and Runs is the number of increasing runs in a sequence. Deterministically finding the median has fragile complexity O(log⁡(Runs)+log⁡log⁡n) and Θ(log⁡(Inv)). Deterministic sorting has fragile complexity Θ(log⁡(Inv)) but it has fragile complexity Θ(log⁡n) regardless of the number of runs.

OriginalsprogEngelsk
TidsskriftTheoretical Computer Science
Vol/bind919
Sider (fra-til)92-102
ISSN0304-3975
DOI
StatusUdgivet - 5. jun. 2022

Bibliografisk note

Funding Information:
This material is based upon work performed while attending AlgoPARC Workshop on Parallel Algorithms and Data Structures at the University of Hawaii at Manoa, in part supported by the National Science Foundation under Grant No. CCF-1930579 . We thank Timothy Chan and Qizheng He for their ideas for improving the randomized selection algorithm. P.B. was partially supported by NSERC . P.C. and J.I. were supported by F.R.S.- FNRS under Grant No. MISU F 6001 1 . R.F. was partially supported by the Independent Research Fund Denmark , Natural Sciences, grant DFF-7014-00041 . J.I. was supported by NSF grant CCF-1533564 . S.L. is Directeur de Recherches du F.R.S.-FNRS.

Funding Information:
This material is based upon work performed while attending AlgoPARC Workshop on Parallel Algorithms and Data Structures at the University of Hawaii at Manoa, in part supported by the National Science Foundation under Grant No. CCF-1930579. We thank Timothy Chan and Qizheng He for their ideas for improving the randomized selection algorithm. P.B. was partially supported by NSERC. P.C. and J.I. were supported by F.R.S.-FNRS under Grant No. MISU F 6001 1. R.F. was partially supported by the Independent Research Fund Denmark, Natural Sciences, grant DFF-7014-00041. J.I. was supported by NSF grant CCF-1533564. S.L. is Directeur de Recherches du F.R.S.-FNRS.

Publisher Copyright:
© 2022 Elsevier B.V.

Fingeraftryk

Dyk ned i forskningsemnerne om 'Fragile complexity of adaptive algorithms'. Sammen danner de et unikt fingeraftryk.

Citationsformater