The maximum order complexity (MOC) of a sequence is a very natural generalization of the well-known linear complexity (LC) by allowing nonlinear feedback functions for the feedback shift register which generates a given sequence. It is expected that MOC is effective to reduce such an instability of LC as an extreme increase caused by the minimum changes of a periodic sequence, i. e. , one-symbol substitution, one-symbol insertion or one-symbol deletion per each period. In this paper we will give the bounds (lower and upper bounds) of MOC for the minimum changes of an m-sequence over GF(q) with period qn-1, which shows that MOC is much more natural than LC as a measure for the randomness of sequences in this case.

From a sequence {ai}i0 over GF(p) with period pn-1 we can obtain another periodic sequence {i}i0 with period pn-2 by deleting one symbol at the end of each period. We will give the bounds (upper bound and lower bound) of linear complexity of {i}i0 as a typical example of instability of linear complexity. Derivation of the bounds are performed by using the relation of characteristic polynomials between {ai}i0 and {ai(j)}i0={ai+j}i0, jGF(p){0}. For a binary m-sequence {ai}i0 with period 2n-1, n-1 a prime, we will give the explicit formula for the characteristic polynomial of {i}i0.