Time bounds for selection. Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L., & Tarjan, R. E. *Journal of Computer and System Sciences*, 7(4):448--461, August, 1973. Paper doi abstract bibtex The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm--PICK. Specifically, no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i, and a new lower bound on the requisite number of comparisons is also proved.

@article{blum_time_1973,
title = {Time bounds for selection},
volume = {7},
issn = {0022-0000},
url = {http://www.sciencedirect.com/science/article/B6WJ0-4RFMC9P-8/2/d76dbc78adcdd9951bf9acd46dc21eea},
doi = {10.1016/S0022-0000(73)80033-9},
abstract = {The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm--PICK. Specifically, no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i, and a new lower bound on the requisite number of comparisons is also proved.},
number = {4},
urldate = {2010-02-05TZ},
journal = {Journal of Computer and System Sciences},
author = {Blum, Manuel and Floyd, Robert W. and Pratt, Vaughan and Rivest, Ronald L. and Tarjan, Robert E.},
month = aug,
year = {1973},
pages = {448--461}
}

Downloads: 0

{"_id":"8vfZxDdaWsszef5Ei","bibbaseid":"blum-floyd-pratt-rivest-tarjan-timeboundsforselection-1973","downloads":0,"creationDate":"2016-12-19T20:50:58.787Z","title":"Time bounds for selection","author_short":["Blum, M.","Floyd, R. W.","Pratt, V.","Rivest, R. L.","Tarjan, R. E."],"year":1973,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","title":"Time bounds for selection","volume":"7","issn":"0022-0000","url":"http://www.sciencedirect.com/science/article/B6WJ0-4RFMC9P-8/2/d76dbc78adcdd9951bf9acd46dc21eea","doi":"10.1016/S0022-0000(73)80033-9","abstract":"The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm--PICK. Specifically, no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i, and a new lower bound on the requisite number of comparisons is also proved.","number":"4","urldate":"2010-02-05TZ","journal":"Journal of Computer and System Sciences","author":[{"propositions":[],"lastnames":["Blum"],"firstnames":["Manuel"],"suffixes":[]},{"propositions":[],"lastnames":["Floyd"],"firstnames":["Robert","W."],"suffixes":[]},{"propositions":[],"lastnames":["Pratt"],"firstnames":["Vaughan"],"suffixes":[]},{"propositions":[],"lastnames":["Rivest"],"firstnames":["Ronald","L."],"suffixes":[]},{"propositions":[],"lastnames":["Tarjan"],"firstnames":["Robert","E."],"suffixes":[]}],"month":"August","year":"1973","pages":"448--461","bibtex":"@article{blum_time_1973,\n\ttitle = {Time bounds for selection},\n\tvolume = {7},\n\tissn = {0022-0000},\n\turl = {http://www.sciencedirect.com/science/article/B6WJ0-4RFMC9P-8/2/d76dbc78adcdd9951bf9acd46dc21eea},\n\tdoi = {10.1016/S0022-0000(73)80033-9},\n\tabstract = {The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm--PICK. Specifically, no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i, and a new lower bound on the requisite number of comparisons is also proved.},\n\tnumber = {4},\n\turldate = {2010-02-05TZ},\n\tjournal = {Journal of Computer and System Sciences},\n\tauthor = {Blum, Manuel and Floyd, Robert W. and Pratt, Vaughan and Rivest, Ronald L. and Tarjan, Robert E.},\n\tmonth = aug,\n\tyear = {1973},\n\tpages = {448--461}\n}\n\n","author_short":["Blum, M.","Floyd, R. W.","Pratt, V.","Rivest, R. L.","Tarjan, R. E."],"key":"blum_time_1973","id":"blum_time_1973","bibbaseid":"blum-floyd-pratt-rivest-tarjan-timeboundsforselection-1973","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/B6WJ0-4RFMC9P-8/2/d76dbc78adcdd9951bf9acd46dc21eea"},"downloads":0,"html":""},"search_terms":["time","bounds","selection","blum","floyd","pratt","rivest","tarjan"],"keywords":[],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}