Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model

The limit laws of three cost measures are derived of two algorithms for finding the maximum in a single-channel broadcast communication model. Both algorithms use coin flips and comparisons. Besides the ubiquitous normal limit law, the Dickman distribution also appears in a natural way. The method of proof proceeds along the line via the method of moments and the “asymptotic transfers,” which roughly bridges the asymptotics of the “conquering cost of the subproblems” and that of the total cost. Such a general approach has proved very fruitful for a number of problems in the analysis of recursive algorithms.