By [1]}, the LZ parse has the smallest
number of phrases among all LZ-like parses of \(T\) . Therefore, to show that
\(z = O(2^b)\) , it suffices to describe an LZ-like parse of \(T\)  with \(O(2^b)\)  phrases.
Indeed, the prefix \(A\)  can be parsed into \(O(2^b)\)  phrases as follows:
all symbols 2 form phrases of length one;
the first length-\(b\)  substring \(00\cdots 0\)  can be parsed into \(b\)  literal phrases 0;
every subsequent binary length-\(b\)  substring \(a_1 a_2 \cdots a_b\)  with \(a_k = 1\) 
and \(a_{k+1} = a_{k+2} = \cdots = a_b = 0\) ,
for some \(k \in \lbrace 1,2,\ldots ,b\rbrace \) , can be parsed into the copying phrase \(a_1 a_2\cdots a_{k-1}\) 
(which must be a prefix of the previous length-\(b\)  binary substring \(a_1 a_2 \cdots a_{k-1}011\cdots 1\) ,
due to the lexicographic order in \(A\) ), the literal phrase 1, and the copying phrase
\(a_{k+1}a_{k+2}\cdots a_b = 00\cdots 0\) . The string \(S_1\)  can be analogously parsed into
\(O(2^b)\)  phrases. Each \(S_i\) , \(i > 2\) , can be expressed as two phrases
that point to \(S_1\) . Thus, we obtain \(z \le |\mathit {LZ}(A)| + |\mathit {LZ}(S_1)| + 2(b/2 - 1) = O(2^b)\) .
