Tree complexity and a doubly exponential gap between structured and random sequences (Q2565197)

The authors introduce a new complexity measure for binary sequences, the tree complexity. They show that the tree complexity grows asymptotically like \(O(2^{2^h})\) (\(h\) height of the tree) for random sequences and like \(O(1)\) for algebraic sequences.