# Running time (Big O) of counting in binary

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?

-
Hint: the number of bits flipped is one more than the number of consecutive 1's at the end of the number. For example, $100\mapsto 101$ (0 ones at end, 1 flip), $100111\mapsto 101000$ (3 ones, 4 flips). – Alex Becker Jan 16 '12 at 22:29
@AlexBecker: How can you tell how many consecutive 1's an arbitrary number has? I don't see how this can help me find Big O. – styfle Jan 16 '12 at 22:36
These aren't arbitrary binary numbers, they're binary numbers from $1$ to $n$. So you should add up the lengths of these sequences for the binary numbers between $1$ and $n$, which shouldn't be too hard. (Hint: every possible sequence of $n$ binary digits is used exactly once when counting from $1$ to $2^n-1$) – Alex Becker Jan 16 '12 at 22:44
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. – styfle Jan 16 '12 at 23:39

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

-
Won't that always apply since it doesn't matter if it's a power of 2? I said earlier that the number of bits used to represent a number is the ceil(log(n+1)). – styfle Jan 18 '12 at 4:56
@styfle: That sounds confused. The total number of bits in each number is not directly related to the number of bits that change. So it's not clear to me what you're bringing that up for. – Henning Makholm Jan 18 '12 at 9:34
Then what does a represent? – styfle Jan 19 '12 at 2:07
@styfle: I'm explicitly considering the case where $n=2^a$ for some $a$. So $a$ is the base-2 logarithm of your $n$. I don't know how you think that could "represent" anything else than that. – Henning Makholm Jan 19 '12 at 18:28
"a bit easier to analyze" +1, made me chuckle. – YoTengoUnLCD Jul 14 at 6:45

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.

-
Strictly speaking, when you claim that T(n) is at most two times $T(2^m)$, you are using the fact $T(2^{m+1}) \le 2T(2^m)$ before you prove it. To avoid this, it is easier to argue in a different order: first you show what $T(2^m)$ is, and then you show that T(n) is within a factor of two from $T(2^m)$. – Tsuyoshi Ito Jan 17 '12 at 1:05
@TsuyoshiIto Yes, that's true. But once you find $T(2^m)$ the negligibility (word?) falls out easily. – Alex Becker Jan 17 '12 at 1:56
Well, that is why I said that it is easier to argue in a different order. – Tsuyoshi Ito Jan 17 '12 at 6:22

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

-