Fragile complexity of adaptive algorithms

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

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review


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.
Original languageEnglish
JournalTheoretical Computer Science
Pages (from-to)92-102
Number of pages11
Publication statusPublished - 5 Jun 2022


  • Algorithms
  • Comparison based algorithms
  • Fragile complexity


Dive into the research topics of 'Fragile complexity of adaptive algorithms'. Together they form a unique fingerprint.

Cite this