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 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 minimum among n distinct elements. The algorithm has a tuning parameter k(n) controlling the
trade-off between the expected fragile complexity fmin(n) of the minimum element and the maximum expected fragile complexity f_rem(n) of the remaining non-minimum elements; if n is clear from the context, we use k instead of k(n). Depending on the choice of k, we obtain interesting trade-offs for the pair ranging from <O(ε^(−1)*loglog(n)), O(nε)> to

.

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(n)) = O(ε−1loglog(n)) comparisons for the minimum and E(f_rem(n)) = O(nε) for the remaining elements.
3. Let k(n) = logn/loglogn. Then RMinimum requires E(f_min(n)) = O(log(n)/loglog(n)) comparisons for the minimum and E(f_rem(n)) = O(log(n)/loglog(n)) for the remaining elements.