Complexity of a loop where j shrinks as j = (j - 1) & i

Question

What is the time complexity of this code snippet? Why, mathematically, is that?

for (int i = 0; i < n; i++) {
    for (int j = i; j > 0; j = (j - 1) & i) {
        System.out.println(j);
    }
}

user_501557 · Answer

The short version:

The runtime of the code is Θ(n^{log₂ 3}), which is approximately Θ(n^1.585).
The derivation involves counting the number of 1 bits set in ranges of numbers.
Your connection to Pascal's triangle is not a coincidence!

Here's the route that I used to work this out. There's a really nice pattern that plays out in the bits of the numbers as you're doing the subtractions. For example, suppose that our number i is given by 10101001 in binary. Here's the sequence of values we'll see for j:

To see the pattern, focus on the columns of the number where there were 1 bits in the original number. Then you get this result:

v v v  v
10101001 1111
10101000 1110
10100001 1101
10100000 1100
10001001 1011
10001000 1010
10000001 1001
10000000 1000
00101001 0111
00101000 0110
00100001 0101
00100000 0100
00001001 0011
00001000 0010
00000001 0001
00000000 0000

In other words, the sequence of values j takes on is basically counting down from the binary number 1111 all the way down to zero!

More generally, suppose that the number i has b(i) 1 bits in it. Then we're counting down from a number made of b(i) 1 bits down to 0, which requires 2^b(i) steps. Therefore, the amount of work the inner loop does is 2^b(i).

That gives us the complexity of the inner loop, but to figure out the total complexity of the loop, we need to figure out how much work is done across all n iterations, not just one of them. So the question then becomes: if you count from 0 up to n, and you sum up 2^b(i), what do you get? Or, stated differently, what is

2^b(0) + 2^b(1) + 2^b(2) + ... + 2^b(n-1)

equal to?

To make this easier, let's assume that n is a perfect power of two. Say, for example, that n = 2^k. This will make this easier because that means that the numbers 0, 1, 2, ..., n-1 all have the same number of bits in them. There's a really nice pattern at play here. Look at the numbers from 0 to 7 in binary and work out what 2^b(i) is for each:

Now look at the numbers from 0 to 15 in binary:

In writing out the numbers from 8 to 15, we're basically writing out the numbers from 0 to 7, but with a 1 prefixed. This means each of those numbers has the one plus the number of 1 bits set as the previous versions, so 2^b(i) is doubled for each of them. So if we know the sum of these terms from 0 to 2^k-1, and we want to know the sum of the terms from 0 to 2^k+1 - 1, then we basically take the sum we have, then add two more copies of it.

More formally, let's define S(k) = 2^b(0) + 2^b(1) + ... + 2^{b(2^k - 1)}. Then we have

S(0) = 1
S(k + 1) = S(k) + 2S(k) = 3S(k)

This recurrence solves to S(k) = 3^k. In other words, the sum 2^b(0) + 2^b(1) + ... + 2^{b(2^k-1)} works out to 3^k.

Of course, in general, we won't have n = 2^k. However, if we write k = log₂ n, then we can get an approximation of the number of iterations at roughly

3^{log₂ k}

= k^{log₂ 3}

≈ k^1.584...

So we'd expect the runtime of the code to be Θ(n^{log₂ 3}). To see if that's the case, I wrote a program that ran the function and counted the number of times the inner loop executed. I then plotted the number of iterations of the inner loop against the function n^{log₂ 3}. Here's what it looks like:

]1

As you can see, this fits pretty well!

So how does connect to Pascal's triangle? It turns out that the numbers 2^b(i) has another interpretation: it's the number of odd numbers in the ith row of Pascal's triangle! And that might explain why you're seeing combinations pop out of the math.

Thanks for posting this problem - it's super interesting! Where did you find it?

user_5426835 · Answer

Here is a Java Code snippet:

int i,j,n,cnt;
int bit=10;
int[] mp = new int[bit+1];
n=(1<


Output:
for 0  // 2^0 - 1
1 0 0 0 0 0 0 0 0 0 0
for 1  // 2^1 - 1
1 1 0 0 0 0 0 0 0 0 0
for 3   // 2^2 - 1
1 2 1 0 0 0 0 0 0 0 0
for 7   // 2^3 - 1
1 3 3 1 0 0 0 0 0 0 0  
for 15  // 2^4 - 1
1 4 6 4 1 0 0 0 0 0 0
for 31  // 2^5 - 1
1 5 10 10 5 1 0 0 0 0 0
for 63   // 2^6 - 1
1 6 15 20 15 6 1 0 0 0 0 
for 127  // 2^7 - 1
1 7 21 35 35 21 7 1 0 0 0 
for 255  // 2^8 - 1
1 8 28 56 70 56 28 8 1 0 0 
for 511  // 2^9 - 1
1 9 36 84 126 126 84 36 9 1 0 
for 1023  // 2^10 - 1
1 10 45 120 210 252 210 120 45 10 1 

So it looks like Pascal triangle…
0C0 
1C0 1C1
2C0 2C1 2C2
3C0 3C1 3C2 3C3
4C0 4C1 4C2 4C3 4C4
5C0 5C1 5C2 5C3 5C4 5C5
6C0 6C1 6C2 6C3 6C4 6C5 6C6
7C0 7C1 7C2 7C3 7C4 7C5 7C6 7C7
8C0 8C1 8C2 8C3 8C4 8C5 8C6 8C7 8C8
9C0 9C1 9C2 9C3 9C4 9C5 9C6 9C7 9C8 9C9
10C0 10C1 10C2 10C3 10C4 10C5 10C6 10C7 10C8 10C9 10C10


In the question above inner loop executes exactly 2^(number set bit) -1 times.
So if we observe we can ses that If k=number of bit,  then N=2^k;
Then Complexity becomes: (kC02^0+kC12^1+kC22^2+kC32^3+ … … … +kCk*2^k) - N
If k=10 then N=2^k=1024 So the complexity becomes as follows:
(10C0*2^0+10C1*2^1+10C2*2^2+10C3*2^3+ … … … +10C10*2^10) - 1024 
=(1*1 +10*2 + 45*4+ 120*8+210*16+252*32+210*64+120*128+45*256+10*512+1*1024) - 1024
=59049 - 1024
=58025 

Here is another code snippet that helps to verify the number 58025.
        int i,j,n,cnt;
        n=1024;
        cnt=0;
        for(i=0;i0; j = (j-1)&i){
                cnt++;
            }
        }
        System.out.println(cnt);

The output of the above code is 58025.

Complexity of a loop where j shrinks as j = (j - 1) & i

2 Answers