Reference machines require non-linear time to maintain disjoint sets

ABSTRACT

This paper describes a machine model intended to be useful in deriving realistic complexity bounds for tasks requiring list processing. As an example of the use of the model, the paper shows that any such machine requires non-linear time in the worst case to compute unions of disjoint sets on-line. All set union algorithms known to the author are instances of the model and are thus subject to the derived bound. One of the known algorithms achieves the bound to within a constant factor.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: A. Borodin and I. Munro, The Computational Complexity of Algebraic and Numeric Problems, Elsevier, New York (1975).
• 3: J. Doyle and R. L. Rivest, "Linear expected time of a simple union-find algorithm," Info. Proc. Letters 5 (1976), 146-148.
• 4: M. J. Fischer, "Efficiency of equivalence algorithms," Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York (1972), 153-168.
• 5: Benrard A. Galler , Michael J. Fisher, An improved equivalence algorithm, Communications of the ACM, v.7 n.5, p.301-303, May 1964 [doi>10.1145/364099.364331]
• 6: J. E. Hopcroft and J. D. Ullman, "Set merging algorithms," SIAM J. Computing 2 (1973), 294-303.
• 7: Mehdi Jazayeri , William F. Ogden , William C. Rounds, The intrinsically exponential complexity of the circularity problem for attribute grammars, Communications of the ACM, v.18 n.12, p.697-706, Dec. 1975 [doi>10.1145/361227.361231]
• 8: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 9: 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
• 10: D. E. Knuth, private communication.
• 11: A. N. Kolmogorov, "On the notion of algorithm," Uspehi Mat. Nauk. 8 (1953), 175 -176.
• 12: A. N. Kolmogorov and V. A. Uspenskii, "On the definition of an algorithm," Uspehi Mat. Nauk. 13 (1958), 3-28, English translation in Amer. Math. Soc. Transl. II Vol. 29 (1963), 217-245.
• 13: A. R. Meyer and L. J. Stockmeyer, "The equivalence problem for regular expressions with squaring requires exponential space," Proc. 13th Annual Symp. on Switching and Automata Theory, 1972, 125-219.
• 14: M. J. Fischer , M. O. Rabin, SUPER-EXPONENTIAL COMPLEXITY OF PRESBURGER ARITHMETIC, Massachusetts Institute of Technology, Cambridge, MA, 1974
• 15: Ronald L. Rivest , Jean Vuillemin, A generalization and proof of the Aanderaa-Rosenberg conjecture, Proceedings of seventh annual ACM symposium on Theory of computing, p.6-11, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803747]
• 16: A. Schonage, REAL-TIME SIMULATION OF MULTIDIMENSIONAL TURING MACHINES BY STORAGE MODIFICATION MACHINES, Massachusetts Institute of Technology, Cambridge, MA, 1973
• 17: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 18: Robert E Tarjan, Applications of path compression on balanced trees., Stanford University, Stanford, CA, 1975
• 19: Robert E Tarjan, Solving path problems on directed graphs., Stanford University, Stanford, CA, 1975
• 20: Robert E Tarjan, Complexity of monotone networks for computing conjunctions, Stanford University, Stanford, CA, 1976
• 21: Andrew Chi-chih Yao, On the average behavior of set merging algorithms (Extended Abstract), Proceedings of the eighth annual ACM symposium on Theory of computing, p.192-195, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803648]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Boundary value problems
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory