A note on Gray code and odd-even merge (Q1102754)

For an integer n let \(\sum^{^ 2\log n}_{0}\epsilon_ j2^ j\) be its binary representation. Then the standard Gray code digits of n are defined by \(\gamma_ j(n)=\epsilon_ j(n)\) if \(j=\lfloor^ 2\log n\rfloor\), \(\gamma_ j(n)=\epsilon_ j(n)+\epsilon_{j+1}(n)\) mod 2 if \(1\leq j<\lfloor^ 2\log n\rfloor\). Furthermore \(\gamma (n):=\sum_{j}\gamma_ j(n).\) Let \(F(k)=\sum_{0\leq j<k}\gamma (j)\). The authors derive upper and lower bounds for F(k) in terms of k. As a consequence they obtain estimates for the complexity of the odd-even merge algorithm of Batcher.