Speedup theorem

In computational complexity theory, a speedup theorem is a theorem that for any algorithm (of a certain class) demonstrates the existence of a more efficient algorithm solving the same problem.

Examples:

Linear speedup theorem, that the space and time requirements of a Turing machine solving a decision problem can be reduced by a multiplicative constant factor.
Blum's speedup theorem, which provides speedup by any computable function (not just linear, as in the previous theorem).

See also

Amdahl's law, the theoretical speedup in latency of the execution of a task at a fixed workload that can be expected of a system whose resources are improved.

References

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.