Jump to content

Speedup theorem

From Wikipedia, the free encyclopedia

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]