Lower Bounds on Merging Networks

ABSTRACT

Let M(m, n) be the minimum number or comparators needed in an (m, n)-merging network. It is shown that M(m, n) ≥ n(lg(m + 1))/2, which implies that Batcher's merging networks are optimal up to a factor of 2 + &egr; for almost all values of m and n. The limit rm = limn→∞ M(m, n)/n is determined to within 1. It is also proved that M(2, n) = [3n/2].

REFERENCES

• 1: BATCHER, K E Sorting networks and their apphcatlons Proc AFIPS 1968 SJCC, Vol 32, AFIPS Press, Montvale, N J , pp 307-314
• 2: FLOYD, R W Permuting reformation in ldeahzed two-level storage In Complexity of Computer Computations, R E Miller and J W Thatcher, Eds, Plenum Press, 1972, pp 105-110
• 3: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 4: 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

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Design, Performance, Theory, Verification