[24] Let : {0, 1} N be a prefix algorithm, that is, a partial computable function with a prefix-free domain. Then the extension

[24] Let φ : {0, 1}∗ → N be a prefix algorithm, that is, a partial computable function with a prefix-free domain. Then the extension complexity of x with respect to φ is defined by Eφ(x) = min{l(p) : x is a prefix of φ(p)}, or Eφ(x) = ∞ if there is no such p.

(a) Show that there is an additively optimal prefix algorithm φ0 such that for any other prefix algorithm φ there is a constant c such that Eφ0 (x) ≤ Eφ(x) + c for all x. Select one such φ0 as reference and set the extension complexity E(x) = Eφ0 (x). Similarly, we can define the conditional extension complexity E(x|y).

(b) Show that for the relation between the extension complexity E and the prefix complexity K(x), with n = l(x), E(x) ≤ K(x) ≤ E(x) + K(n) + O(1) ≤ E(x) + l ∗(n) + O(1).
Comments. Source: [S.K. Leung-Yan-Cheong and T.M. Cover, IEEE Trans. Inform. Theory, IT-24(1978), 331–339].