
Accession Number : AD0721701
Title : An Improved Lower Bound for the BoseNelson Sorting Problem.
Descriptive Note : Technical note,
Corporate Author : STANFORD UNIV CALIF STANFORD ELECTRONICS LABS
Personal Author(s) : Van Voorhis,David C.
Report Date : FEB 1971
Pagination or Media Count : 14
Abstract : The paper presents a constructive proof that the minimum number of comparators required for an Ninput sorting network is at least the summation from K=1 to N (log of N to the base 2). This lower bound represents a linear improvement over the informationtheoretic bound of (log of N factorial to the base 2). (Author)
Descriptors : (*COMPUTER LOGIC, LOGIC CIRCUITS), COMPARATORS, DATA PROCESSING, INPUT OUTPUT DEVICES
Subject Categories : Computer Hardware
Distribution Statement : APPROVED FOR PUBLIC RELEASE