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:

See also

edit
  • 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

edit