Vrftjkry

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++;

    }



} 

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^kbinom nk - sum_k=0^n binom nk = 1 + (1+2)^n - 2^n = 3^n+1-2^n$$
Hope my analysis is correct.

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

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} = nsum_{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)& ile j-1<j$. Study some example to figure out how many times the inner loop is executed.