An O(n+k) algorithm for ordered retrieval from an associative memory

The problem of retrieving an ordered list of k words that satisfy a given search condition from an associative memory of m words of n bits each is addressed. A fast ordered retrieval algorithm is proposed, along with a logic design for a cellular associative memory which mechanizes the algorithm. The algorithm is of time complexity O(n+k). By contrast, the fastest previously known algorithms, by M.H. Lewis (see RCA Rev., vol.23, p.215-29 (1962)) and C.V. Ramamoorthy, J.L. Turner, and B.W. Wah (see ibid., vol.27, no.9, p.800-15 (1978)), are of time complexities O( k×log n) and O(k×n), respectively