purposes. For a given binary sequence we estimate its linear complexity profile in terms of
the correlation measure, which was introduced by Mauduit and Sárközy. We apply this result
to certain periodic sequences including Legendre sequences, Sidelnikov sequences and
other sequences related to the discrete logarithm.