2
$\begingroup$

What is the total running time of counting from 1 to $n$ in binary if the time needed to add 1 to the current number $i$ is proportional to the number of bits in the binary expansion of $i$ that must change in going from $i$ to $i+1$?

I can't figure out how to do this. If the number $n$ has $m$ bits, then we can say $n = 2^m - 1$ so the amount of bits used to represent the number is $m = \lceil log_2(n+1) \rceil$. The most amount of bits that will be flipped when incrementing a number is all $m$ bits. That's all I got. Where do I go from here?

  • 0
    Well I meant just because I can find the amount of bits used to represent n, doesn't mean I know how many consecutive 1's it has. I am still confused.2012-01-16

3 Answers 3

2

The case where $n=2^a$ for some $a$ is a bit easier to analyze. Let's observe the list of binary numbers for $a=3$:

0001 0010 0011 0100 0101 0110 0111 1000 

We're interested in how many times there's a bit that changes. The trick is to count not one number a time but one bit position at a time:

  • The ones bit changes for every number, so it flips $n$ times.
  • The twos bit changes for every second number, so it flips $n/2$ times.
  • The fours bit changes one time out of four so it flips $n/4$ times.

And so forth -- the total number of flips is $\sum_{i=0}^a \frac{n}{2^i} = n \sum_{i=0}^a 2^{-i} < 2n$ where the last inequality is because $\sum_{i=0}^a 2^{-i}$ is a prefix of the infinite geometric series with sum $2$.

Now, can you prove there are also $\le 2n$ flips when $n$ is not a power of $2$?

  • 1
    "*a **bit** easier to analyze*" +1, made me chuckle.2016-07-14
0

Let $T(n)$ be the running time of counting from $1$ to $n$. In order to determine $O(T(n))$, we need only look at values if $n$ such that $n=2^m$ for some $m\in\mathbb{N}$, as for any $n$ we have some $m$ such that $2^m\leq m<2\times 2^m=2^{m+1}$ and $T(n)$ is increasing, so we can make use of the fact that $O(T(n))$ ignores the constant $2$. So what is $T(2^m)$? Well, it is precisely $2^m$ plus the combined lengths of all the sequences of ones at the end of the numbers in $[1,2^m-1]$, as for each number in this range the number of bits flipped is one more than the number of consecutive ones at the end of the number. For example, $100\mapsto 101$ (0 ones at end, 1 flip), $100111\mapsto 101000$ (3 ones, 4 flips). Since each possible sequence of ones and zeroes of length $m$ occurs exactly once in the range $[1,2^m-1]$, we can simply count them out. There are $2^{m-2}$ sequences which end in $01$, $2^{m-3}$ sequences ending in $001$, the same number for those ending in $010$ and $011$, so on and so forth. I leave it to you to figure out a formula for the number of sequences ending in precisely x ones (which means you want to count the number of sequences with a zero then $x$ ones, except in the case $2^m-1=11\cdots1$) and to find the weighted sum in order to get the running time.

  • 0
    Well, that is why I said that it is easier to argue in a different order.2012-01-17
0

Here's an exact formula:

For any positive integer $n,$ let $T(n)$ be the total number of bits that get flipped as one counts from $1$ to $n.$ Then $T(n)= 2n - \text{(the number of }1\text{'s in the binary representation of }n)-1.$ It's easy to prove this by induction:

Basis:

$T(1)= 0 = 2 \cdot 1 - 1- 1.$

Induction Step:

For convenience, write $B(n)$ for the number of $1$'s in the binary representation of $n.$

Assume that $T(n)= 2n - B(n)-1.$ We need to show that $T(n+1)= 2n+2 - B(n+1)-1.$

If the binary representation of $n$ ends with exactly $k \; 1$'s, then we can write $n$ in binary as $a_1 \dots a_j 0 1 1 1 \dots 1$ (with $k \; 1$'s at the end). (Note that $k$ may be $0,$ but that's OK.) So $n+1$ in binary is $a_1 \dots a_j 1 0 0 0 \dots 0$ (with $k \; 0$'s at the end). Looking at the number of $1$'s in each of these, you can see that $B(n+1)=B(n)-k+1$ (because there are $k \; 1$'s in $n$ that are lost in moving to $n+1,$ but there is one $0$ in $n$ that becomes a $1$ in $n+1$).

We need to flip $k+1$ bits to count from $n$ to $n+1,$ so \begin{align}T(n+1)&=T(n)+k+1 \\\\&=(2n - B(n)-1)+k+1 \\\\&=2n - B(n+1) + 1 \\\\&=2n+2 - B(n+1)-1,\end{align} as desired, completing the proof by induction.

So now we know that for every positive integer $n,$ $T(n)= 2n - \text{(the number of }1\text{'s in the binary representation of }n)-1.$

Since $T(n) < 2n$ for all positive integers $n,$ we have $T(n)=O(n).$ To see that this is the best possible estimate of that sort, observe that $B(n)$ is at most $\lfloor \log_2(n)\rfloor+1,$ the total number of bits in the binary representation of $n.$ So \begin{align} T(n) &= 2n-B(n)-2 \\\\& \ge 2n-\lfloor \log_2(n)\rfloor-3. \end{align}

Incidentally, it's probably worth mentioning that this isn't what is usually called linear running time, because that refers to a running time that is $O(n)$ where $n$ is the number of bits in the input. In this problem, $n$ is value of the input, not its size. If we measure running time in the usual way, based on the size of the input, then counting from $1$ to $n$ takes exponential running time (exponential in the number of bits in the binary number $n).$