Establishing lower bounds on algorithms: a survey
AFIPS '72 (Spring): Proceedings of the May 16-18, 1972, spring joint computer conference, page 471--481. New York, NY, USA, ACM, (1972)DOI: 10.1145/1478873.1478936
Abstract
Algorithms for various computations have been known and studied for centuries, but it is only recently that much theoretical attention has been devoted to the analysis of algorithms. Turing machines and recursive functions were the first approaches, but these models, which provide much interesting mathematics, do not look at the problem from a practical standpoint. In "real" computing, no one uses Turing machines to evaluate polynomials or to multiply matrices, and little of practical significance is obtained from that approach. On the other hand, recent work has led to more realistic models and, correspondingly, to more practical results. Most of the results cannot be considered to be truly practical, but, all of them were motivated by practical considerations.
Description
Establishing lower bounds on algorithms
