[39]

(a) Show that l

∗(x) = log x + log log x + ··· (all positive terms) satisfies 

x 2−l

∗(x) < ∞.

(b) Show that for all x we have K+(x) ≤ l

∗(x) + O(1) (K+ as in Exercise 3.3.1).

(c) Show that for most x we have K+(x) = l

∗(x) + O(1).

Comments. Hint for Item (b): use Item (a). Source: attributed to T.M.

Cover [P. G´acs, Lecture Notes on Descriptional Complexity and Randomness, Manuscript, Boston University, 1987].