Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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