I am reading the lecture notes and have a question. I am trying to understand the beginning of Section 3 on page 2.
Problem: Given an input stream $\sigma$, compute (or approximate) its length $m$.
Naive solution: $O(\log m)$ bits, exact solution.
I don't understand why it is not $O(m)$ bits but $O(\log m)$ bits. Any help would be greatly appreciated.