On the Nth linear complexity of automatic sequences

We prove that any (not ultimately periodic) q-automatic sequence over Fq has Nth linear complexity of order of magnitude N. For some famous sequences including the Thue-Morse and Rudin-Shapiro sequence we determine the exact values of their Nth linear complexities. These are non-trivial examples of predictable sequences with Nth linear complexity of largest possible order of magnitude.