On Effective Procedures for Speeding Up Algorithms
Manuel Blum · Journal of the ACM · 1971
This paper is concerned with the nature of speedups.Let f be any recursive function.We show that there is no effective procedure for going from an algorithm f o r f to another algorithm for f that is significantly faster on all but a finite number of inputs.On the other hand, for a large class of functions f, one can go effectively from any algorithm for f to one that is faster on at least infinitely many integers.Finally, if one has an algorithm for a given function f, and if there is an algorithm which is faster on all but a finite number of inputs, then even though one cannot get this faster algorithm effectively, one can still obtain a pseudospeedup: This is a very fast algorithm which computes a variant of the function, one which differs from the original function on a finite number of inputs.