, hay otra máquina que resuelve el mismo problema en tiempo
Suponga que la máquina de Turing M resuelve el problema en
símbolos de cinta y
Construya una nueva máquina M' con
en la máquina M' representa la secuencia de células
de la máquina M (note que estos grupos coinciden parcialmente).
En un paso computacional, M' simula la computación de M hasta que la cabeza de M' salga del grupo de células a la izquierda o la derecha (esta simulación se puede hacer en un solo paso porque M no puede estar en más de
Una sutileza final es que porque los cachos se solapan, cada transición entre cachos en M debe ser transformado en
transiciones entre células en M' para tomar en cuenta la
símbolos diferentes que se podría haber escrito en la célula que pertenece a los dos cachos.
La construcción requiere que cada paso computacional en M' corresponde a por lo menos 2 pasos en M. Entonces M' toma no más de
Debe ser fácil ver como generalizar la prueba a todos los valores de
El teorema del aumento de velocidad linear es la razón que la teoría de complejidad hace caso omiso de factores lineares y representa la complejidad de algoritmos con la cota superior asintótica