{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:22:20Z","timestamp":1777454540386,"version":"3.51.4"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,3,1]],"date-time":"2009-03-01T00:00:00Z","timestamp":1235865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,3]]},"abstract":"\n Given a set of\n n<\/jats:italic>\n elements, each of which is colored one of\n c<\/jats:italic>\n colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal\/unequal color comparisons of elements. We focus on the expected number of color comparisons when the\n \n c\n n<\/jats:sup>\n <\/jats:italic>\n colorings are equally probable. We analyze an obvious algorithm, showing that its expected performance is\n c<\/jats:italic>\n 2<\/jats:sup>\n +\n c<\/jats:italic>\n \u2212 2\/2\n c<\/jats:italic>\n n<\/jats:italic>\n \u2212\n O<\/jats:italic>\n (\n c<\/jats:italic>\n 2<\/jats:sup>\n ), with variance \u0398(\n c<\/jats:italic>\n 2<\/jats:sup>\n n<\/jats:italic>\n ). We present and analyze an algorithm for the case\n c<\/jats:italic>\n = 3 colors whose average complexity on the 3\n \n n<\/jats:sup>\n <\/jats:italic>\n equally probable inputs is 7083\/5425\n n<\/jats:italic>\n +\n O<\/jats:italic>\n (\u221a\n n<\/jats:italic>\n ) = 1.3056\u2026\n n<\/jats:italic>\n +\n O<\/jats:italic>\n (\u221a\n n<\/jats:italic>\n ), substantially better than the expected complexity 5\/3\n n<\/jats:italic>\n +\n O<\/jats:italic>\n (1) = 1.6666\u2026\n n<\/jats:italic>\n +\n O<\/jats:italic>\n (1) of the obvious algorithm. We describe a similar algorithm for\n c<\/jats:italic>\n =4 colors whose average complexity on the 4\n \n n<\/jats:italic>\n <\/jats:sup>\n equally probable inputs is 761311\/402850\n n<\/jats:italic>\n +\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n ) = 1.8898\u2026\n n<\/jats:italic>\n +\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n ), substantially better than the expected complexity 9\/4\n n<\/jats:italic>\n +\n O<\/jats:italic>\n (1) = 2.25\n n<\/jats:italic>\n +\n O<\/jats:italic>\n (1) of the obvious algorithm.\n <\/jats:p>","DOI":"10.1145\/1497290.1497293","type":"journal-article","created":{"date-parts":[[2009,4,6]],"date-time":"2009-04-06T16:34:22Z","timestamp":1239035662000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Average-case analysis of some plurality algorithms"],"prefix":"10.1145","volume":"5","author":[{"given":"Laurent","family":"Alonso","sequence":"first","affiliation":[{"name":"INRIA-Lorraine, Vandoeuvre-l\u00e8s-Nancy, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edward M.","family":"Reingold","sequence":"additional","affiliation":[{"name":"Illinois Institute of Technology, Chicago, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,3,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.035"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Alexanderson G. L. Klosinski L. F. and Larson L. C. 1985. The William Lowell Putnam Mathematical Competition Problems and Solutions: 1965--1984. The Mathematical Association of America Washington D.C. Alexanderson G. L. Klosinski L. F. and Larson L. C. 1985. The William Lowell Putnam Mathematical Competition Problems and Solutions: 1965--1984. The Mathematical Association of America Washington D.C.","DOI":"10.1090\/prb\/030"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367067"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367066"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90135-V"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794275914"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-0060-0"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v30:1\/2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1975.11993974"},{"key":"e_1_2_1_10_1","volume-title":"The Art of Computer Programming, Volume 1: Fundamental Algorithms","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1997a. The Art of Computer Programming, Volume 1: Fundamental Algorithms , 3 rd ed. Addison Wesley Longman Publishing Co., Inc. , Redwood City, CA . Knuth, D. E. 1997a. The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA.","edition":"3"},{"key":"e_1_2_1_11_1","volume-title":"The Art of Computer Programming, Volume 2: Seminumerical Algorithms","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1997b. The Art of Computer Programming, Volume 2: Seminumerical Algorithms , 3 rd ed. Addison-Wesley Longman Publishing Co., Inc. , Boston, MA . Knuth, D. E. 1997b. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd ed. Addison-Wesley Longman Publishing Co., Inc., Boston, MA.","edition":"3"},{"key":"e_1_2_1_12_1","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1998. The Art of Computer Programming, Volume 3: Sorting and Searching , 2 nd ed. Addison Wesley Longman Publishing Co., Inc. , Redwood City, CA . Knuth, D. E. 1998. The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA.","edition":"2"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.05.014"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.06.004"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1497290.1497293","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1497290.1497293","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:40Z","timestamp":1750250740000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1497290.1497293"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["10.1145\/1497290.1497293"],"URL":"https:\/\/doi.org\/10.1145\/1497290.1497293","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3]]},"assertion":[{"value":"2006-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}