Linear speedup theorem

In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any k-tape Turing machine solving a problem in time f(n), there is another k-tape machine that solves the same problem in time at most f(n)/c + 2n + 3, where k > 1.^[1]^[2] If the original machine is non-deterministic, then the new machine is also non-deterministic. The constants 2 and 3 in 2n + 3 can be lowered, for example, to n + 2.^[1]

The theorem also holds for Turing machines with 1-way, read-only input tape and $k\geq 1$ work tapes.^[3]

For single-tape Turing machines, linear speedup holds for machines with execution time at least $n^{2}$ . It provably does not hold for machines with time $t(n)\in \Omega (n\log n)\cap o(n^{2})$ .^[3]

^ ^a ^b Christos Papadimitriou (1994). "2.4. Linear speedup". Computational Complexity. Addison-Wesley.
^ Thomas A. Sudkamp (1994). "14.2 Linear Speedup". Languages and Machines: An Introduction to the Theory of Computer Science. Addison-Wesley.
^ ^a ^b Wagner, K.; Wechsung, G. (1986). Computational Complexity. Springer. ISBN 978-9027721464.

[papadi-1] Christos Papadimitriou (1994). "2.4. Linear speedup". Computational Complexity. Addison-Wesley.

[sudkamp-2] Thomas A. Sudkamp (1994). "14.2 Linear Speedup". Languages and Machines: An Introduction to the Theory of Computer Science. Addison-Wesley.

[WW-3] Wagner, K.; Wechsung, G. (1986). Computational Complexity. Springer. ISBN 978-9027721464.

[1]

[2]

[3]