# Blum's speedup theorem in big-O format?

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

• it seems Blums speedup thm is often stated not in big-O notation as on wikipedia but just noticed that mathworld states the big-O version. – vzn Feb 6 '14 at 2:05

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.