{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:10Z","timestamp":1759638430264},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2014,7,9]],"date-time":"2014-07-09T00:00:00Z","timestamp":1404864000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2014,9]]},"abstract":"<jats:p>We define a sequence of tree-indexed processes closely related to the operation of the <jats:monospace>QuickSelect<\/jats:monospace> search algorithm (also known as <jats:monospace>Find<\/jats:monospace>) for all the various values of <jats:italic>n<\/jats:italic> (the number of input keys) and <jats:italic>m<\/jats:italic> (the rank of the desired order statistic among the keys). As a \u2018master theorem\u2019 we establish convergence of these processes in a certain Banach space, from which known distributional convergence results as <jats:italic>n<\/jats:italic> \u2192 \u221e about\n<jats:list list-type=\"number\"><jats:list-item><jats:label>(1)<\/jats:label><jats:p>the number of key comparisons required<\/jats:p><jats:p>are easily recovered\n<jats:list list-type=\"number\"><jats:list-item><jats:label>(a)<\/jats:label><jats:p>when <jats:italic>m\/n<\/jats:italic> \u2192 \u03b1 \u2208 [0, 1], and<\/jats:p><\/jats:list-item><jats:list-item><jats:label>(b)<\/jats:label><jats:p>in the worst case over the choice of <jats:italic>m<\/jats:italic>.<\/jats:p><\/jats:list-item><\/jats:list>\nFrom the master theorem it is also easy, for distributional convergence of<\/jats:p><\/jats:list-item><jats:list-item><jats:label>(2)<\/jats:label><jats:p>the number of symbol comparisons required,<\/jats:p><\/jats:list-item><\/jats:list>\nboth to recover the known result in the case (a) of fixed quantile \u03b1 and to establish our main new result in the case (b) of worst-case <jats:monospace>Find<\/jats:monospace>.<\/jats:p><jats: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 <jats:italic>L<jats:sup>p<\/jats:sup><\/jats:italic> or almost surely) than convergence in distribution. Extensions to <jats:monospace>MultipleQuickSelect<\/jats:monospace> are discussed briefly.<\/jats:p>","DOI":"10.1017\/s0963548314000121","type":"journal-article","created":{"date-parts":[[2014,7,9]],"date-time":"2014-07-09T09:37:27Z","timestamp":1404898647000},"page":"805-828","source":"Crossref","is-referenced-by-count":4,"title":["QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find"],"prefix":"10.1017","volume":"23","author":[{"given":"JAMES ALLEN","family":"FILL","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JASON","family":"MATTERER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,7,9]]},"reference":[{"key":"S0963548314000121_ref17","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1995290402551"},{"key":"S0963548314000121_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771562"},{"key":"S0963548314000121_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9294-3"},{"key":"S0963548314000121_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2009.10.013"},{"key":"S0963548314000121_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90009-6"},{"key":"S0963548314000121_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0021900200014650"},{"key":"S0963548314000121_ref1","volume-title":"Probability and Measure","author":"Billingsley","year":"1995"},{"key":"S0963548314000121_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009241"},{"key":"S0963548314000121_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_62"},{"key":"S0963548314000121_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0046-2"},{"key":"S0963548314000121_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S000186780000639X"},{"key":"S0963548314000121_ref22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813658"},{"key":"S0963548314000121_ref11","first-page":"321","article-title":"Find (algorithm 65).","volume":"4","author":"Hoare","year":"1961","journal-title":"Commun. Assoc. Comput. Mach."},{"key":"S0963548314000121_ref5","doi-asserted-by":"publisher","DOI":"10.1214\/12-AAP866"},{"key":"S0963548314000121_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"key":"S0963548314000121_ref14","first-page":"185","article-title":"On the number of comparisons in Hoare's algorithm \u2018FIND\u2019.","volume":"33","author":"Kodaj","year":"1997","journal-title":"Studia Sci. Math. Hungar."},{"key":"S0963548314000121_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0167-7152(95)00139-5"},{"key":"S0963548314000121_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S000186780002735X"},{"key":"S0963548314000121_ref6","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v15-734"},{"key":"S0963548314000121_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548302005138"},{"key":"S0963548314000121_ref13","unstructured":"Knuth D. E. (1972) Mathematical analysis of algorithms. In Information Processing 71: Proc. IFIP Congress, Ljubljana, 1971, North-Holland, pp. 19\u201327."},{"key":"S0963548314000121_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00150-B"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,21]],"date-time":"2019-04-21T21:11:48Z","timestamp":1555881108000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000121\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,9]]},"references-count":22,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["S0963548314000121"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000121","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,9]]}}}