Speedup theorem
From Wikipedia, the free encyclopedia
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)+n+2 of that resource, where c > 0 is arbitrary.
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)).
 |
This disambiguation page lists mathematics articles associated with the same title. If an internal link led you here, you may wish to change the link to point directly to the intended article. |
