A note on Gray code and odd-even merge (Q1102754)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on Gray code and odd-even merge |
scientific article |
Statements
A note on Gray code and odd-even merge (English)
0 references
1987
0 references
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.
0 references
sum-of-digits function
0 references
Batcher's odd-even merge
0 references
merging algorithms
0 references
Gray code
0 references