Even–Paz protocol

in 1984, Shimon Even and Azaria Paz published their improved algorithm, whose run-time complexity is only O(n log n).

[1] The algorithm uses a divide-and-conquer strategy, it is possible to achieve a proportional division in time O(n log n).

Thanks to the divide-and-conquer strategy, the number of iterations is only O(log n), in contrast to O(n) in the Last Diminisher procedure.

Several years after the publication of the Even–Paz algorithm, it was proved that every deterministic or randomized proportional division procedure assigning each person a contiguous piece must use Ω(n log n) actions.

The following randomized version of the recursive halving procedure achieves a proportional division using only O(n) mark queries on average.