Hommel's procedure in linear time

Hommel's and Hochberg's procedures for familywise error control are both derived as shortcuts in a closed testing procedure with the Simes local test. Hommel's shortcut is exact but takes quadratic time in the number of hypotheses. Hochberg's shortcut takes only linear time after the P-values are sorted, but is conservative. In this paper, we present an exact shortcut in linear time on sorted P-values, combining the strengths of both procedures. The novel shortcut also applies to a robust variant of Hommel's procedure that does not require the assumption of the Simes inequality.