QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find

Source abstract

We define a sequence of tree-indexed processes closely related to the operation of the QuickSelect search algorithm (also known as Find ) for all the various values of n (the number of input keys) and m (the rank of the desired order statistic among the keys). As a ‘master theorem’ we establish convergence of these processes in a certain Banach space, from which known distributional convergence results as n → ∞ about (1) the number of key comparisons required are easily recovered (a) when m/n → α ∈ [0, 1], and (b) in the worst case over the choice of m . From the master theorem it is also easy, for distributional convergence of (2) the number of symbol comparisons required, both to recover the known result in the case (a) of fixed quantile α and to establish our main new result in the case (b) of worst-case Find . Our techniques allow us to unify the treatment of cases (1) and (2) and indeed to consider many other cost functions as well. Further, all our results provide a stronger mode of convergence (namely, convergence in L p or almost surely) than convergence in distribution. Extensions to MultipleQuickSelect are discussed briefly.