Time Complexity and Output of the code

Question

It is very difficult for me to analyse the time complexity and output of the following code.I literally was not able to find even the output. I know that

1<< N

is left shift 1 by N bit .

#include <stdio.h>
#define N 3
int main() {
 int array[N] = {1,2,3};
 int i,j;
 for ( i=1; i<(1<<N); i++) {
      for( j=0; j<N; j++) {
           if((1<<j)&i) {
                printf("%d", array[j]);
           }
      }
      printf("\n");
 }
 return 0;
}

• Q1) How many times the if successfully executes in this instance of c program. And how many time when N=n, with n being a positive integer?
• Q2) What is the output? In other words, how is the execution taking place and finally arrive at Output. In short - how the output is obtained?
• Q3) What will be the complexity when N is large

What I have tried

when N=3 ,

1<<N

will be 8 So outer loop execute for 8 times and inner loop execute for 3 time

But how does

if((1<<j)&i) 

works ?

When N is n , positive integer I think the complexity will be O(n 2^n)

Please help me analysing the code and complexity of the program

Answer 1

Q1) If condition will be tested N * (2^N-1) times.

The body of the if will execute for each set bit in i.

In this instance, i takes values in the range [1, 8]. In this range, 3 values have 1 bit set; 3 values have 2 bits set; 1 value has 3 bits set. You have 3 * 1 + 3 * 2 + 1 * 3 = 12 executions of if body.

For N = n > 0, you can think how many different numbers of length n have exactly k bits set. This is combinations of n elements in groups of k, which is the Newton binomial (n over k).

So, executions (n) = sum (i * (n over i)) for i in [0, n].

This is executions (n) = n * 2^(n-1)

Proof:

sum (i*(n over i)) for i in [0, n] = sum (i*(n over i)+(n-i)*(n over n-i)) for i in [0, n/2]

But (n over i) = (n over n-i)

Therefore, we can write the previous expression as

sum ((i + (n-i))*(n over i)) = n * sum (n over i) for i in [0, n/2]

We know sum (n over i) for all i in [0, n] = 2^n

As it is symmetric, the sum in half the range is 2^n/2 = 2^(n-1)

Therefore,

executions (n) = n * 2^(n-1)

For example, executions (3) = 3 * 2^2 = 12

Q2)

The output is all possible combinations of the elements in array, regardless of the order, excluding the empty set.

The array has size N and the program generates all possible binary numbers of length N, except zero.

It matches bit positions with array positions, and prints out the values of the array in positions corresponding to set bits. Of course, if you do this for all possible N-bit values, you have all possible combinations of set bits and thus all possible combinations of array elements (excluding the empty set).

You could include the empty set by initialising i to zero, but you would only get an empty line.

How does the program match set bits with array positions?

Ok j goes from 0 to N-1, thus scanning all bit/array positions.

To check the value of bit j you compute the bitwise and between the current value of i and a mask consisting of only a one at position j and zeroes at all other positions. Therefore, the bitwise and will result in zero for all positions but j, and the actual value of the bit in position j of i.

1 << j generates the mask; it just shifts a single 1 to its desired position.

Then, (1 << j) & i is the biwise and of the mask with i. If the result is nonzero, jth bit in i is 1. If the result is zero, the bit is 0.

Q3)

Well, N is a constant. So, strictly speaking, complexity is O (1).

But I understand you are interested in complexity considering N the variable size of the problem.

In this case, the outer loop is executed 2^N - 1 times, and the inner loop, N times. This is N * (2^N - 1) in O (N*2^N).

If printf dominates, we know it's executed (ignoring line feeds) N * 2^(N-1) times = (N * 2^N) / 2, also in O (N*2^N).

Answer 2

Your analysis is mostly correct regarding the number of iterations of the outer loop and the if test. As long as N is such that 1 << N does not cause an overflow (thereby invoking undefined behavior), the if is executed N * (2^N - 1) times.

The question Q1 is more subtile: how many times does the if execute successfully for any positive integer?

• language lawyers will say that if executes successfully as long as it does not invoke undefined behavior. In other words: as long as n < CHAR_BIT * sizeof(int) - 1. Indeed for a large N, (1 << N) invokes undefined behavior as it causes arithmetic overflow. For example if type int is 32-bit wide, the maximum value for which 1 << N is defined is 30.
• the question probably refers to the condition: how many times does the test evaluate to a non zero value? The outer loops iterates over all non-zero numbers with N bits or less. The inner loop iterates over all bit numbers, testing every bit once. The total number of if tests is n * 2ⁿ - n. each bit is tested for every possible combination: half the tests evaluate to 0 and half to non-zero, while the n tests for value 0 are omitted. The answer to question Q1 is n * 2^n-1 - n, which can be factored as n * (2^n-1 - 1).

Half the tests succeed and invoke printf(). Simplifying the negligible values and constant factor 2, the time-complexity of this function for large values of n comes out as O(n * 2ⁿ).

Answer 3

Q1) I think it is a similar question to Q3

Q2) The code which is inside of for loop will be executed how many integer 'i' has 1 bits. if N = n, 'i' is in the range of 1 to 2^n - 1. It means you can easily think this way

There are n bit slots. 'i' will iterate all cases which n bit slots can make except 0.

For example, In the case of N = 3, there are 3 bits slots OOO and 'i' will iterate all cases except 0. 001, 010, 011, 100, 101, 110, 111.

As I mentioned, the code which is inside of for loop will be executed starting with the lowest index and print a number when '1' bit on.

N = 3,

1

2

12

3

13

23

123

Q3) O(N*2^N). It's too large to calculate I think.