Link between plain complexity and prefix complexityWe want to prove:
C(s)+ O(1)< K(s)< C(s)+2 × log(C(s))+ O(1)
The first inequality is a consequence of the invariance theorem, since prefix machines are particular Turing machines.
A minimal program p that generates s is such that |p|= C(s). A self-delimited program can be obtained by coding p in a self-delimited way (e.g. by prefixing it by its double-coded length). This double-length coded version of p is self-delimited. Therefore, K(s)<2log(|p|)+|p|+ O(1), which is the second inequality.