Fragile Complexity of Adaptive Algorithms

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

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-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 Θ(logk), 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(loglogk) 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)+loglogn) and Θ(log(Inv)). Deterministic sorting has fragile complexity Θ(log(Inv)) but it has fragile complexity Θ(logn) regardless of the number of runs.
Original languageEnglish
Title of host publicationInternational Conference on Algorithms and Complexity
Number of pages14
VolumeLNCS 12701
PublisherSpringer
Publication date10 May 2021
Pages144-157
ISBN (Print)978-3-030-75241-5
ISBN (Electronic)978-3-030-75242-2
Publication statusPublished - 10 May 2021
SeriesLNCS
Volume12701

Keywords

  • Algorithms
  • Fragile complexity
  • Comparison based algorithms

Cite this