Fragile complexity of adaptive algorithms
Jacob, Riko; id_orcid 0000-0001-9470-1809, Rolf Fagerberg, Prosenjit K. Bose, Pilar Cano, John Iacono, Stefan Langerman · IT University Of Copenhagen (IT University of Copenhagen) · 2022
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 $\Theta(\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 $k$th smallest element has expected fragile complexity $O(\log\log k)$ for the element selected. Deterministically finding the minimum element has fragile complexity $\Theta(\log(\INV))$ and $\Theta(\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 $\Theta(\log (\INV))$. Deterministic sorting has fragile complexity $\Theta(\log (\INV))$ but it has fragile complexity $\Theta(\log n)$ regardless of the number of runs.