Speedup theorem
|
|
In computational complexity theory, a speedup theorem is a theorem that considers some algorithm solving a problem and demonstrates the existence of a faster algorithm solving the same problem (or more generally, an algorithm using less of any resource, not just time).
The linear speedup theorem for Turing machines proves that given any machine solving a problem using f(n) of some resource, there is another machine that solves the same problem using cf(n) of that resource, where c > 0.
Blum's speedup theorem demonstrates the existence of a problem such that if any algorithm can solve it in time O(f(n)), there is another algorithm that solves it in time O(log f(n)).
The quadratic speedup theorem for quantum computers proves that if a deterministic computer can carry out a search in time O(f(n)) then a quantum computer can carry out the same search in time O(√f(n)).de:Speedup-Theorem