In computational complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

, a speedup theorem is a theorem that considers some algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 solving a problem and demonstrates the existence of a more efficient algorithm solving the same problem.

The linear speedup theorem for Turing machines shows that the space and time requirements of a Turing machine solving a decision problem

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...

 can be reduced, roughly speaking, by any multiplicative constant factor.

Blum's speedup theorem

Blum's speedup theorem

In computational complexity theory Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about the complexity of computable functions....

provides speedup by any computable function (not just linear, as in the previous theorem). Given the desired speedup function, it deduces the existence of a decision problem such that any algorithm solving it can be sped up.