// Workers AI · dad joke modeWhat did the speedup theorem say to its friend? "You're accelerating our friendship.

For the theorem that some mathematical proofs can be drastically shortened in stronger axiom systems, see Gödel's speed-up 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.