[20] Analyze the integer function K(x|n) with n = l(x).

(a) Show that there is a constant c such that there are infinitely many x such that K(x|n) ≤ c.

(b) Let h = n − C(x|n). Show that K(x|n) ≤ C(x|n) + K(h|n) + O(1).

(c) Use Item

(b) to show that K(x|n) ≤ n + O(1) for all x.

(d) Show that K(x|n) ≤ C(x|n) + log n + O(1).