ABSTRACT
We remark that this is tight. A counting argument shows that there are many x with K{x) > |x| + log |x|. (The readers are advised to prove this for themselves.4 In fact for finite strings this would be the typical notion of randomness used if we demanded prefix-free complexity.) There is one good tradeoff, namely, now K(xy) < K(x) + K{y) + 0(1) . For these and other facts we refer the reader to Li-Vitanyi [48] or Fortnow [32].
