Fragile complexity of adaptive algorithms

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.