Complexity of an algorithm with two cases

Question

What is the complexity for following algorithm if

1) $f(i, j) = (j - 1)\ \&\ j$

2) $f(i, j) = (j - 1)\ \&\ i$

s = 0

for(i = 0; i <= pow(2, n); i++){

    for(j = i; j > 0; j = f(i, j)) {
        s++;
    }

} 

Answer 1

For the second case, let's explore an example : let's choose $i=203=11001011_2$, we find the following sequence for $j$ :

$11001011$

$11001010$

$11001001$

$11001000$

$11000011$

$11000010$

$11000001$

$11000000$

$10001011$

etc

So everything is as if the zeroes where ignored : you count from $x$ to $0$, where $x$ is written whit only the ones in the binary writing of $i$.

If $i$ has $k$ bits set to $1$, then $x=2^k-1$ is the time spent in the inner loop. So the complexity is $$1+\sum_k=0^n (2^k-1)\binom nk = 1+\sum_k=0^n 2^k\binom nk - \sum_k=0^n \binom nk = 1 + (1+2)^n - 2^n = 3^n+1-2^n$$ Hope my analysis is correct.

Answer 2

In both cases, the inner loop runs forever because j remains stuck at 0.

Answer 3

Let's see the first case : as was said in the comments, $f(i,j)=(j-1)\& j$ consists in changing the lest significant bit set to $1$ in $j$ to $0$. So repeating operation $j=f(i,j)$ until $j=0$ does erase the $1$ bits of $j$ from right to left, you make as many passages in the loop as there are bits set to $1$ in $j$.

As $j$ is initially $i$ in the inner loop, you have to count the number of bits set to $1$ in $i$. As $i$ goes from $0$ to $2^n-1$, $i$ has $n$ bits. The number of $i$ for which the binary form contains $k$ bits set to $1$ is $\binom nk$, for you have to choose the places of the ones. For those $i$, the inner loop is executed $k$ times. So the number of times the instruction $s++$ is executed is $$\sum_{k=0}^n k.\binom nk = \sum_{k=1}^n n.\binom{n-1}{k-1} = n\sum_{k'=0}^{n-1} \binom{n-1}{k'} = n.2^{n-1}$$ to which you have to add $1$ because the upper bound is $2^n$, not $2^n-1$, so there is one more iteration for $i=2^n$.

The second case is a little bit more difficult, but you can benefit from the fact that the initial value of $j$ is $i$. So the first time, the rightmost bit set to one in $j$ is set to $0$. After that, you have to figure out what will happen. The loop must end at some time, because $(j-1)\& i\le j-1<j$. Study some example to figure out how many times the inner loop is executed.