es c(n) in this message is maximized when the phrases are as short as possible, meaning that there are 2m phrases of size m for each m. This yields an upper bound for c(n), which can be developed according to: c(n)<<2" -1-24-1-20 =22+1-2, T.M. Cover and J.A. Thomas, Elements of Information Theory (New York: John Wiley & Sons, 1991), p. 320-1. Lempel-Ziv distinct parsing < 2 K +1 where K > 1 is assumed. Consider next the more complex case where the message length satisfies LK n n < LK+1. We can write n = LK+AK, where AK is bounded by the difference LK+1 - LK = K2K+2 + 2 - - [(K - 1)2 x + 2] - = (K+1)2K, or AK (K + 1)2 K The parsing generates a certain number of phrases of length < K, with the rest being of length K + 1. The maximum number of phrases of length K + 1 is 2K+1, which is strictly greater than Ak/(K+1). Thus, the upper bound for c(n) is now given by: The next step is to bound K (find the maximum value of K) with respect to n. Assume most generally that Lk <n < LK+1. The first inequality with Eq. (I3) gives The lower bound 2K in Eq. (I6) is found by setting K = 1 then K > 1. There is equality in the first case, and in the second case we have (K - - 1)2K+1+2>212>212 The result in Eq. (I6) implies: K < logn. Appendix I The second inequality with Eqs. (I3) and (I7) gives < Lk+1 = K2K+2 + 2 K2K+2 = (K + 2)2k+2 < (logn + 2)2 x 42 Hence, which, with the condition n > develops into = log - 3 (I10) If we assume n > 4, we have log n + 2 < 2 log n and, consequently, log(log. +2) < log(210gn) : = log log n + 1. Substituting this inequality in Eq. (I10) yields -12(1) (I11) = (1 En) log n, ===================== (I12) We now require that K - 1 1>0 (a condition which has been overlooked in the refer- ence). 2 Since we already assumed n >4 (log n > 2), this extra requirement is equivalent to En < 1. Letting n = 29 (q > 0 and real) and substituting in Eq. (I12), we obtain the new condition log q 1<q - 4. As easily checked, a sufficient condition is q > 8 or n > 128 (the exact condition being n > 109). Under the condition