the general case, a string X of length n can have any number k of 1 bits, with 0 < k/n < 1. We first observe that the integer k is defined by the sum of the aj bits forming the string, namely, if X = Anan-1 a2a1 (aj=0or 1) we have k= . Second, we observe that since k n n we have log <<logn. Based on these two observations, the general approximation formula giving the upper bound for the complexity K(x)n) of any binary string of length n defined by X = Anan-1 a2a1 (aj = 0 or 1), is: K(x)n) <2logn +nf (7.21) To recall, Eq. (7.21) represents the Stirling approximation of the exact definition: K(x/n)<2logn+logCh (7.22) 20 Eq. (A9) in Appendix A. Applying Stirling's formula yields, after some algebra: In the limit n >> 1, and after regrouping the terms, the formula reduces to: where Algorithmic entropy and Kolmogorov complexity String X Figure 7.4 Upper bound of conditional complexity K(x)n) for each binary string x of exactly n bits (n = 2 to n = 7), as defined by Eq. (7.21) with the Stirling approximation (open symbols), and as defined by Eq. (7.22) without approximation (dark symbols). In each series of size n, the strings x are ordered according to their equivalent decimal value. Figure 7.4 shows plots of the upper bound of K (x I n) for each binary string of exactly n bits, according to (a) the Stirling approximation in Eq. (7.21) with c" = log(1/2) + C (taking C = 0), and (b) the corresponding exact definition in Eq. (7.22), also taking C = 0. For each series of length n, the strings X are ordered according to their equivalent decimal value (e.g., x = 11 corresponds to x = 1011 in the series n = 4, x = 01011 in the series n = 5, X = 001011 in the series n = 6, etc.). We first observe from the figure that the upper bound of K(x I n) oscillates between different values. For even bit sequences (n even), the absolute minima are obtained for f(u) = 0 or Ch = 1, and correspond to the cases where all bits are identical. The absolute maxima are obtained for f(u) = 1 or Ch = 0.5, which corresponds to the cases where ther