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

• Record Type: Journal Article
• Authors: FILL, JAMES ALLEN; MATTERER, JASON; Broutin, Nicolas; Fill, James Allen; Nebel, Markus; Ward, Mark Daniel
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 5(2014:Sep.)
• Page Start: 805
• Page End: 828
• Publication Date: 2014-09
• Subjects: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000121
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>We define a sequence of tree-indexed processes closely related to the operation of the <monospace>QuickSelect</monospace> search algorithm (also known as <monospace>Find</monospace>) for all the various values of <italic>n</italic> (the number of input keys) and <italic>m</italic> (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 <italic>n</italic> → ∞ about <list list-type="order"><list-item><label>(1)</label><p>the number of key comparisons required</p><p>are easily recovered <list list-type="order"><list-item><label>(a)</label><p>when <italic>m/n</italic> → α ∈ [0, 1], and</p></list-item><list-item><label>(b)</label><p>in the worst case over the choice of <italic>m</italic>.</p></list-item></list> From the master theorem it is also easy, for distributional convergence of</p></list-item><list-item><label>(2)</label><p>the number of symbol comparisons required, </p></list-item></list> 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 <monospace>Find</monospace>.</p> <p>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 <italic>L<sup>p</sup></italic> or almost surely) than convergence in distribution. Extensions to <monospace>MultipleQuickSelect</monospace> are discussed briefly.</p> </abstract>