RMinimum-Algorithm

A Python implementation of the RMinimum algorithm.

The algorithm is presented in the paper Fragile Complexity of Comparison-Based Algorithms by Prof. Dr. Ulrich Meyer and others in 2018. A reworked version of it can can be found on arXiv.org.

It introduces the algorithms RMinimum and RMedian and also the concept of fragile complexity, i.e. the amount of times an element has been compared during the process of the algorithm.

The package was published on PyPI and tested on Travis CI.

Algorithm

In the following we present RMinimum, a randomized recursive algorithm for finding the min- imum among n distinct elements. The algorithm has a tuning parameter k(n) controlling the trade-off between the expected fragile complexity f_min(n) of the minimum element and the maxi- mum expected fragile complexity f_rem(n) of the remaining none-minimum elements; if n is clear from the context, we use k instead of k(n). Depending on the choice of k, we obtain interest- ing trade-offs for the pair hE [fmin (n)] , max E [frem (n)]i ranging from <O(ε−1loglog(n)), O(n_ε)> to <O(log(n)/loglog(n)), O(log(n)/loglog(n))>. Given a total ordered set X of n distinct elements, RMinimum performs the following steps:

1. Randomly group the elements into n/2 pairwise-disjoint pairs and use one comparison for each pair to partition X into two sets L and W of equal size: W contains all winners, i.e. elements that are smaller than their partner. Set L gets the losers, who are larger than their partner and hence cannot be the global minimum.
2. Partition L into n/k random disjoint subsets L_1 , . . . , L_n/k each of size k and find the minimum element mi in each Li using a perfectly balanced tournament tree (see Theorem 1).
3. Partition W into n/k random disjoint subsets W_1 , . . . , W_n/k each of size k and filter out all elements in W_i larger than mi to obtain W_0 = U_i {w|w ∈ Wi ∧ w < mi }.
4. If |W_0| ≤ log2 (n_0) where n0 is the initial problem size, find and return the minimum using a perfectly balanced tournament tree (see Theorem 1). Otherwise recurse on W_0.

Complexity

1. Runtime: RMinimum requires linear work w(n) = O(n).
2. Let k(n) = n_ε for 0 < ε ≤ 1/2. Then RMinimum requires E(f_min) = O(ε−1loglogn) comparisons for the minimum and E(f_rem) = O(n_ε) for the remaining elements.
3. Let k(n) = logn/loglogn. Then RMinimum requires E(f_min) = O(logn/loglogn) comparisons for the minimum and E(f_rem) = O(logn/loglogn) for the remaining elements.