## 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.

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.

Originalsprog | Engelsk |
---|---|

Tidsskrift | Theoretical Computer Science |

Vol/bind | 915 |

Sider (fra-til) | 92-102 |

Antal sider | 11 |

ISSN | 0304-3975 |

DOI | |

Status | Udgivet - 5 jun. 2022 |