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