[Solved]: Blum's speedup theorem in big-O format?

Problem Detail: 

Is there a way to state Blum's speedup theorem in terms of Big-O (Landau) notation?

Asked By : vzn

Answered By : Yuval Filmus

Blum's speedup theorem implies that for any computable function $f(n,T)$ there is a computable predicate $\Pi$ such that for every program $P_1$ for $\Pi$ there is another program $P_2$ for $\Pi$ whose running time satisfies $f(n,T(P_2)) \leq T(P_1)$. In particular, there exists a computable predicate $\Pi$ such that for every program $P_1$ computing it there is another program $P_2$ computing it and running in time $T(P_2) = o(T(P_1))$.

But the theorem is much stronger: for example, for some other predicate $\Pi$, the guarantee is $T(P_2) = O(\log T(P_1))$; and for another predicate $\Pi$, the guarantee is $T(P_2) = O(T(P_1)/n)$; and so on.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21342

3.2K people like this

 Download Related Notes/Documents