On the complexity of computing the measure of ∪[ai,bi]

ABSTRACT

The decision tree complexity of computing the measure of the union of n (possibly overlapping) intervals is shown to be &OHgr;(n log n), even if comparisons between linear functions of the interval endpoints are allowed. The existence of an &OHgr;(n log n) lower bound to determine whether any two of n real numbers are within ∈ of each other is also demonstrated. These problems provide an excellent opportunity for discussing the effects of the computational model on the ease of analysis and on the results produced.

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: Bentley, J.L. Divide and conquer algorithms for closest point problems in multidimensional space. Rep. No. TR-76-103, U. of North Carolina, Chapel Hill, N.C., Dec. 1976.
• 3: Dobkin, D., and Lipton, R. On the complexity of computations under varying sets of primitives. Comp. Sci. Tech. Rep. No. 42, Yale U., New Haven, Conn., 1975.
• 4: Fredman, M.L. On computing the length of longest increasing subsequences. Discrete Math. 11 (1975), 29-35.
• 5: Klee, V. Can the measure of U{ai, bi} be computed in less than O(n log n) steps? Amer. Math. Monthly 84, 4 (April 1977), 284-285.
• 6: 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
• 7: Rabin, M.O. Proving simultaneous positivity of linear forms. J. Comptr. Syst. Sci 6, 6 (Dec. 1972), 639-650.
• 8: Yuval, G. Finding nearest neighbours. Inform. Proc. Letters 5, 3 (Aug. 1976), 63-65.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

General Terms:
Design, Management, Measurement, Performance, Theory

Keywords:
analysis of algorithms, combinatorial problems, computational complexity, computational models, computational problems, decision tree programs, lower bounds