On Effective Procedures for Speeding Up Algorithms

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.