Linear speedup theorem

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, the linear speedup theorem for <a href="/facts/Turing_machine/ojCtglYu">Turing machines</a> states that given any <a href="/facts/Real_number/R02gw5Pb">real</a> 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.
If the original machine is <a href="/facts/Non-deterministic_Turing_machine/zv2x6XPG">non-deterministic</a>, then the new machine is also non-deterministic.
The constants 2 and 3 in 2n + 3 can be lowered, for example, to n + 2.
The theorem also holds for Turing machines with 1-way, <a href="/facts/Read-only_Turing_machine/AlWgvJbA">read-only</a> input tape and 
 
 
 
 k
 ≥
 1
 
 
 {\displaystyle k\geq 1}
 
 work tapes.
For single-tape Turing machines, linear speedup holds for machines with execution time at least 
 
 
 
 
 n
 
 2
 
 
 
 
 {\displaystyle n^{2}}
 
. It provably does not hold for machines with time 
 
 
 
 t
 (
 n
 )
 ∈
 Ω
 (
 n
 log
 ⁡
 n
 )
 ∩
 o
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle t(n)\in \Omega (n\log n)\cap o(n^{2})}
 
.

Linear speedup theorem open-in-new

Linear speedup theorem