The Complexity of Algorithms
Mark D Atkinson · Cambridge University Press eBooks · 1996
The modern theory of algorithms dates from the late 1960s when the method of asymptotic execution time measurement began to be used. It is argued that the subject has both an engineering and a scientific wing. The engineering wing consists of well understood design methodologies while the scientific one is concerned with theoretical underpinnings. The key issues of both wings are surveyed. Finally some personal opinions on where the subject will go next are offered. Introduction The concept of ‘algorithm’ is the oldest one in computer science. It is of such antiquity in fact that it may appear presumptuous for computer scientists to claim it as part of their subject. However, although algorithms have been part of scientific tradition for millennia it was not until the computer era that they assumed the major role they now play in these traditions. Indeed, until a few decades ago most scientists would have been hard-pressed to give significant examples of any algorithms at all. Yet algorithms have been routinely used for centuries. Generations of school children learnt the algorithms for addition, subtraction, multiplication, and division and could use them with all the blinkered competence of a mechanical computer. Few of them would ever have stopped to wonder how it was that they allowed the computation, in a matter of moments, of quantities far beyond what could be counted or imagined. These elementary algorithms are amazingly efficient but it was not until the computer era that questions of efficiency were seriously addressed. Had they been so addressed the mathematical curriculum might have been different.