Linear speedup theorem

A theorem stating that a Turing machine running in time T(n) can be simulated in roughly T(n)/c time for any fixed constant c, with an additive cost proportional to input length.

Connect

Turing machine: An abstract machine that computes by reading and writing symbols on a tape according to finite-state rules. The theorem changes the machine model’s tape encoding and transition rules.
Deterministic Turing machine: A Turing machine whose next action is uniquely determined by its current state and scanned symbols. The standard statement concerns deterministic computation under a fixed machine model.
Hartmanis–Stearns theorem: A foundational result connecting time complexity on multitape Turing machines with formal complexity classes. Its machine-based complexity framework helped establish the setting for speedup results.
Blum speedup theorem: A theorem showing that certain computable problems have no ultimately fastest algorithm under suitable complexity measures. It gives unbounded iterative improvements, unlike the linear theorem’s chosen constant factor.
P (complexity class): The class of decision problems solvable by a deterministic algorithm in polynomial time. Reducing a polynomial-time bound by a constant leaves its polynomial growth unchanged.
Multitrack Turing machine: A Turing machine whose tape cells hold tuples of symbols, enabling several tracks to share one tape position. Multiple tracks can bundle simulated tape contents into fewer machine steps.
Running time: The number of computation steps taken by a program or machine on a given input. The speedup applies to this step count, not to output length or memory use.
Juraj Hromkovič: A Slovak computer scientist known for research and textbooks on algorithms and computational complexity. His expositions explain the theorem through explicit machine simulations.
Time hierarchy theorem: A theorem establishing that more computation time permits solving problems unavailable within sufficiently smaller time bounds. It separates complexity classes rather than optimizing constants for one machine.
Big-O equivalence: The relation in which two functions have the same asymptotic growth up to constant factors. The theorem supports treating constant-factor runtime changes as asymptotically immaterial.