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 c omplexity of a binary de Bruijn sequence of length 2(n) is bounded below by 2(n-1) + n and above by 2(n-1) for n greater than or equal to 3. We briefl y survey the known knowledge in this area. Same new results are also presen ted, in particular, it is shown that for each interval of length 2(right pe rpendicular log n left perpendicular + 1), in the above range, there exist binary de Bruijn sequences of length 2(n) with linear complexity in the int erval.