Fragile Complexity of Comparison-Based Algorithms

Peyman Afshani, Rolf Fagerberg, David Hammer, Riko Jacob, Irina Kostitsyna, Ulrich Meyer, Manuel Penschuck, Nodari SitchinavaarXiv 2019 · arXiv

Abstract

Standard algorithmic analysis focuses on total work, often overlooking the "wear and tear" on individual data elements. This paper formalizes fragile complexity, defined as the maximum number of comparisons any single element participates in during an algorithm's execution. We establish tight bounds for fundamental problems like finding the minimum, selection, and sorting. Our results reveal a significant gap between deterministic and randomized settings: while deterministic algorithms are often limited by logarithmic depth, randomized approaches can achieve significantly lower fragile complexity, such as finding a minimum with only constant expected comparisons for the minimum element.

Introduction: The Cost of Participation

In classical complexity theory, we typically optimize for total comparisons or parallel depth. However, in many practical scenarios, the elements being compared are "fragile." Consider a wine-tasting competition where each comparison consumes a portion of the bottle, or a sports tournament where every match increases the risk of injury. In these cases, the quality of the final result depends on minimizing the burden on individual elements.

Fragile complexity $f(n)$ addresses this by measuring the maximum load on any single input element. This metric provides a new lens through which to evaluate comparison-based algorithms, distinguishing between those that distribute work evenly and those that "overwork" specific elements.

Methodology

To explore the limits of fragile complexity, we employ several theoretical techniques:

  • Adversary Arguments: These are used to establish deterministic lower bounds. For instance, we prove that any deterministic algorithm finding the minimum must subject that element to at least $\log n$ comparisons.
  • Randomized Sampling: Our "SampleMinimum" algorithm uses random subsets as filters to reduce the comparison load on the actual minimum element.
  • Comparator Networks: We analyze the relationship between fragile complexity and the depth of sorting networks. While network depth provides an upper bound, general algorithms can often achieve better performance or lower total work.
  • Expander-based Partitioning: For deterministic selection, we utilize $\epsilon$-halvers derived from expander graphs to partition sets without overloading individual elements.
A comparator network illustrating how elements (x1-x8) are compared across different stages. The depth of such a network provides an upper bound for fragile complexity.

Key Results

Our findings demonstrate a comprehensive landscape of upper and lower bounds across various problems. A central insight is the "Power of Randomization." For finding the minimum, a deterministic algorithm is constrained to $\Theta(\log n)$ fragile complexity. In contrast, a randomized algorithm can find the minimum such that the minimum element itself participates in only $O(1)$ comparisons on average.

Summary of upper and lower bounds for fragile complexity f(n) and total work w(n) across fundamental problems.

For the selection problem (finding the median), we show that comparison-based algorithms are strictly more powerful than comparator networks. They can match the fragile complexity (depth) of the best networks while maintaining optimal $O(n)$ total work, whereas networks like AKS require $O(n \log n)$.

Discussion and Future Work

While we have established tight bounds for many problems, several challenges remain. The deterministic results for selection and sorting rely on expander graphs (e.g., AKS networks), which are theoretically optimal but practically cumbersome due to large constant factors. Developing "expander-free" deterministic algorithms with similar bounds is a key open question.

Additionally, while we achieved $O(1)$ expected fragile complexity for the minimum, the best randomized bound for the median is $O(\log \log n)$. Whether the median can also be found with constant expected comparisons on the median element remains an intriguing open problem. Future research could also extend this "fragile" framework to other domains, such as computational geometry.

Summary updated

Abstract

We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the maximal number of comparisons any individual element takes part in. We give a number of upper and lower bounds on the fragile complexity for fundamental problems, including Minimum, Selection, Sorting and Heap Construction. The results include both deterministic and randomized upper and lower bounds, and demonstrate a separation between the two settings for a number of problems. The depth of a comparator network is a straight-forward upper bound on the worst case fragile complexity of the corresponding fragile algorithm. We prove that fragile complexity is a different and strictly easier property than the depth of comparator networks, in the sense that for some problems a fragile complexity equal to the best network depth can be achieved with less total work and that with randomization, even a lower fragile complexity is possible.
BibTeX
@misc{afshani2019fragile,
  author = {Peyman Afshani and Rolf Fagerberg and David Hammer and Riko Jacob and Irina Kostitsyna and Ulrich Meyer and Manuel Penschuck and Nodari Sitchinava},
  title = {{Fragile Complexity of Comparison-Based Algorithms}},
  year = {2019},
  eprint = {1901.02857},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1901.02857},
}
Figure