  We estimate the maximum-order complexity of a binary sequence in terms of its
correlation measures. Roughly speaking, we show that any sequence with small
correlation measure up to a sufficiently large order $k$ cannot have very small
maximum-order complexity.
