abstract:In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any Turing machine solving a problem in time f(n), there is another machine that solves the same problem in time at most cf(n) + n + 2.