# Why it is not $O(m)$ but $O(\log m)$?

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.

Here $O(\log m)$ denotes the space complexity of the algorithm. We can represent a natural number $m$ in $O(\log m)$ space trivially.

For example, when we express numbers in base-2 system (binary number), $m$ is expressed in $\lceil \log_2 m \rceil$ bits. (e.g., 5 is 101 in binary notation. $\lceil\log_2 5\rceil$ digits.)

As a side note, $m$ is expressed in $O(m)$ space if we use base-1 system. (e.g., 5 is 11111 in unary notation. 5 digits.)

As a definition, the input size of a problem is the minimum number of bits $(\{0,1\})$ needed to encode the input of the problem. Since it is given that input length $|\sigma|=m$ , you should have $Ceil ( {\log_2 m})$ bits to encode $\sigma$.