Fragile Complexity of Adaptive Algorithms

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 $\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.

Appears at proceedings of the 12th International Conference on Algorithms and Complexity (CIAC 2021)