# Complexity of Thue-Morse Sequence

Consider the alphabet $\mathcal{A}=\{0,1\}$ and the substitution $\phi$ given by $\phi(0)=01$, $\phi(1)=10$. Let $t$ be the point given by $t=\lim_{n\rightarrow\infty}\phi^n(0)$. Then $t$ is the Thue-Morse sequence; its first couple of characters are $0110100110010\ldots$.

We define the complexity of a word $u$ as a map $F_u:\mathbb{N}\rightarrow\mathbb{N}$, such that for all $n\in\mathbb{N}$, $F_u(n)$ is equal to the number of distinct subwords of $u$ of length $n$.

Has anyone calculated the complexity function of the Thue-Morse sequence? I have tried to find some sources, but have not succeeded. Any references are most welcome.

According to the French Wikipedia page on the Prouhet-Thue-Morse sequence, the complexity function $c(n)$ of the Thue-Morse sequence is the sequence A005942 on OEIS. It can be computed as follows. For $n \geqslant 1$, let $k \geqslant 0$ be the integer such that $2^k + 1 \leqslant n \leqslant 2^{k + 1}$ and let $r$ be such that $n = 2^k + r$ with $1\leqslant r\leqslant 2^{k}$. Then $$c(n)= \begin{cases} 3\cdot 2^{k}+4(r-1)&{\text{if }}1 \leqslant r \leqslant 2^{k-1},\\ 4\cdot 2^{k}+2(r-1)&{\text{if }}2^{k-1}+1\leqslant r \leqslant 2^{k}. \end{cases}$$ Moreover, $c(n) \leqslant \frac{10}{3}n$ for all $n$. Relevant references (from the OEIS):