  Expansion complexity and maximum order complexity are both finer measures of
pseudorandomness than the linear complexity which is the most prominent quality
measure for cryptographic sequences. The expected value of the $N$th maximum
order complexity is of order of magnitude $\log N$ whereas it is easy to find
families of sequences with $N$th expansion complexity exponential in $\log N$.
This might lead to the conjecture that the maximum order complexity is a finer
measure than the expansion complexity. However, in this paper we provide two
examples, the Thue-Morse sequence and the Rudin-Shapiro sequence with very
small expansion complexity but very large maximum order complexity. More
precisely, we prove explicit formulas for their $N$th maximum order complexity
which are both of largest possible order of magnitude $N$. We present the
result on the Rudin-Shapiro sequence in a more general form as a formula for
the maximum order complexity of certain pattern sequences.
