 |
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).
- 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.
 | This computer science article is a stub. You can help Wikipedia by expanding it. |
|
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).
- 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.
|
| This computer science article is a stub. You can help Wikipedia by expanding it. |