= Linear speedup theorem
{title2=$T_c(n)\leq T(n)/c+n+O(1)$}
{wiki}
For every constant $c>0$, a deterministic <multitape Turing machine> with more than one tape and <time complexity> bounded by $T(n)$ has an equivalent machine with the same tape count and bound $T(n)/c+n+O(1)$, allowing a larger finite control and tape <alphabet>. Blocks of old symbols become single new symbols, and finite control implements blocks of old steps. The linear overhead accounts for initial <input> packing. If $T(n)/n\to\infty$, the overhead can be absorbed to obtain any fixed constant speed increase for sufficiently large <inputs>. This does not supply unlimited speed increases for operations on fixed hardware.<Computational Complexity, slides 1 by Paul W. Goldberg (2023)>[Slides 47–48, PDF pp. 62–63: formal statement and block-simulation construction]{ref}
Back to article page
