Average-case analysis of some plurality algorithms

ABSTRACT

Given a set of n elements, each of which is colored one of c 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 cⁿ colorings are equally probable. We analyze an obvious algorithm, showing that its expected performance is c² + c − 2/2c n − O(c²), with variance Θ(c²n). We present and analyze an algorithm for the case c = 3 colors whose average complexity on the 3ⁿ equally probable inputs is 7083/5425n + O(&sqrt;n) = 1.3056…n + O(&sqrt; n), substantially better than the expected complexity 5/3n + O(1) = 1.6666…n + O(1) of the obvious algorithm. We describe a similar algorithm for c =4 colors whose average complexity on the 4ⁿ equally probable inputs is 761311/402850n + O(log n) = 1.8898…n + O(log n), substantially better than the expected complexity 9/4n + O(1) = 2.25n + O(1) of the obvious algorithm.

REFERENCES

• 1: Martin Aigner , Gianluca De Marco , Manuela Montangero, The plurality problem with three colors and more, Theoretical Computer Science, v.337 n.1-3, p.319-330, 9 June 2005 [doi>10.1016/j.tcs.2004.12.035]
• 2: Gerald L Alexanderson , Leonard F Klosinski , Loren C Larson, The William Lowell Putnam mathematical competition: problems and solutions: 1965-1984, Mathematical Association of America, Washington, DC, 1985
• 3: Laurent Alonso , Edward M. Reingold, Average-case lower bounds for the plurality problem, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-17, June 2008 [doi>10.1145/1367064.1367067]
• 4: Laurent Alonso , Edward M. Reingold, Determining plurality, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-19, June 2008 [doi>10.1145/1367064.1367066]
• 5: Laurent Alonso , Edward M. Reingold , René Schott, Determining the majority, Information Processing Letters, v.47 n.5, p.253-255, Oct. 8, 1993 [doi>10.1016/0020-0190(93)90135-V]
• 6: Laurent Alonso , Edward M. Reingold , René Schott, The Average-Case Complexity of Determining the Majority, SIAM Journal on Computing, v.26 n.1, p.1-14, Feb. 1997 [doi>10.1137/S0097539794275914]
• 7: Fan Chung , Ron Graham , Jia Mao , Andrew Yao, Oblivious and Adaptive Strategies for the Majority and Plurality Problems, Algorithmica, v.48 n.2, p.147-157, May 2007 [doi>10.1007/s00453-007-0060-0]
• 8: Zdeněk Dvořák , Vít Jelínek , Daniel Král' , Jan Kynčl , Michael Saks, Probabilistic strategies for the partition and plurality problems, Random Structures & Algorithms, v.30 n.1-2, p.63-77, January 2007 [doi>10.1002/rsa.v30:1/2]
• 9: Hillman, A. P. 1975. The William Lowell Putnam mathematical competition. Amer. Math. Monthly 82, 9 (Nov.), 905--912.
• 10: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 11: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 12: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 13: Daniel Král' , Jiří Sgall , Tomáš Tichý, Randomized strategies for the plurality problem, Discrete Applied Mathematics, v.156 n.17, p.3305-3311, October, 2008 [doi>10.1016/j.dam.2008.05.014]
• 14: Nikhil Srivastava , Alan D. Taylor, Tight bounds on plurality, Information Processing Letters, v.96 n.3, p.93-95, 15 November 2005 [doi>10.1016/j.ipl.2005.06.004]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Theory

Keywords:
Algorithm analysis, majority problem, plurality problem