Linear complexity of de Bruijn sequences-old and new results

The linear complexity of a de Bruijn sequence is the degree of the shortest linear recursion which generates the sequence. It is well known that the complexity of a binary de Bruijn sequence of length 2ⁿ is bounded below by 2^n-1+n and above by 2^n-1 for n⩾3. We briefly survey the known knowledge in this area. Some new results are also presented, in particular, it is shown that for each interval of length 2^{[log n]+1} in the above range, there exist binary de Bruijn sequences of length 2ⁿ with linear complexity in the interval