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?
 A: 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$?
A: 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.
A: 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).$
