Article ID Journal Published Year Pages File Type
4648557 Discrete Mathematics 2010 8 Pages PDF
Abstract

We answer the following question: What is the discrepancy of the lexicographically least binary de Bruijn sequence? Here, “discrepancy” refers to the maximum (absolute) difference between the number of ones and the number of zeros in any initial segment of the sequence. We show that the answer is Θ(2nlogn/n)Θ(2nlogn/n).

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
The discrepancy of the lex-least de Bruijn sequence
Authors
, ,