Accession Number:

AD0744631

Title:

Bounds to Complexities of Networks for Sorting and for Switching,

Descriptive Note:

Corporate Author:

ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB

Personal Author(s):

• Muller,David E.
• Preparata,Franco P.

Report Date:

1972-05-01

Pagination or Media Count:

18.0

Abstract:

A network which sorts n numbers when used to sort numbers of only two sizes, 0 and 1, can be regarded as forming the n frontal unate symmetric boolean functions of n arguments. When sorting networks are constructed from comparator modules they appear to require 1 delay time or number of levels of order log of n to the base 2 squared, 2 size or number of elements of order log of n to the base 2 squared, and 3 formula length or number of literals of order n log of n to the base 2. If one permits the use of negations in constructing the corresponding boolean functions, these three measures of complexity can be reduced to the orders of log of n to the base 2, n, and n to the 5th power respectively. The latter network however is incapable of sorting numbers and may be thought of as merely counting the number of inputs which are 1. One may incorporate this network, however, in a larger network which does sort and in time proportional to only log of n to the base 2. Author

Descriptors:

• (*MATHEMATICAL LOGIC
• COMPUTER PROGRAMMING)
• SWITCHING CIRCUITS
• SPECIAL FUNCTIONS(MATHEMATICAL)
• GATES(CIRCUITS)
• COMPARATORS
• INEQUALITIES
• THEOREMS

Subject Categories:

• Theoretical Mathematics
• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE