Running time (Big O) of counting in binary

Question

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?

Answer 1

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

Answer 2

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.