0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.)

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.