  However, there is a limit on how well any algorithm can compress a string. If \(\lvert\sigma\rvert\) is the length of \(\sigma\), say that a string \(\sigma\) is compressed by \(f\) if there is an \(f\)-description \(\delta\) such that \(\sigma = f(\delta)\) and \(\lvert\delta\rvert \lt \lvert\sigma\rvert\). If a useful decompression algorithm is such that for some fixed \(k\), \(\lvert f(\delta)\rvert \le \lvert\delta\rvert + k\), so that \(f\)-descriptions are at least \(k\) shorter than the sequence to be compressed, then it follows that very few strings usefully compress. For there are \(2^l\) strings \(\sigma\) such that \(\lvert\sigma\rvert = l\); so there are at most \(2^{l - k} f\)-descriptions; since \(f\) is a function, there are at most \(2^{l-k}\) compressible strings. As a proportion of all strings of length \(l\), then, there are at most \(2^{l-k}/2^{l} = \frac{1}{2}^{k}\) compressible strings . This means that as the amount of compression required increases, the number of sequences so compressible decreases exponentially. Even in the most pitiful amount of compression, \(k = 1\), we see that at most half the strings of a given length can be compressed by any algorithm \(f\).