Time complexity and output

Question

#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;
}

• A. How many times the if successfully executes in this instance of c program. And how many time when $N = n \;\; , n \; \text{ is a positive integer }$ ?
• B. What is the output?
• C. What will be the complexity when $N$ is large.

Comments

#include <stdio.h>

#define N 3
int cnt = 0;
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) {
                    cnt++;
                    printf("%d", array[j]);
               }
          }
          printf("\n");
     }
     printf("count = %d\n",cnt );
     return 0;
}

Actually, cnt value is needed in terms of n

---

Yes, that is good otherwise needed to count as it grows polynomially.

---

#include <stdio.h>

#define N 3
int cnt = 0;
int if_run_count = 0;
int f() {
     if_run_count++;
     return 1;
}


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(f() && (1<<j)&i) {
                    cnt++;
                    printf("%d", array[j]);
               }
          }
          printf("\n");
     }
     printf("if inside count = %d\n",cnt );
     printf("if run count = %d\n",if_run_count);
     return 0;
}

QS need cnt value only but not if_run_count.

Answer 1

How many times the if successfully executes in this instance of c program. 
What is the output?

Here the complexity of the code is coming to be $O(n2^{n})$

Answer 2

For this code 

#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;
}

Output is like : 

1,2,12,3,13,23,123 = Total $2^{n}-1$ = $2^{3}-1$ = 7 output sequences 

---

If we modify the code like :

#include <stdio.h>

#define N 5

int main() {
     int array[N] = {1,2,3}; //array[N] = {1,2,3,0,0}
     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;
}

Output is like : 

Many output Sequences = $2^{n}-1$ (Growing exponentially for every N)

Comments

@Kapil SIR  is the complexity O(n2^n) ?  because outer loop executes for O(2^n) and inner loop executed for O(n) time

Correct me if my understanding is wrong

---

Yes, I think SO. But let me check if $N.2^{N} = O(2^{N})$

In this case, if this is true, then $\frac{N.2^{N}}{2^{N}}$ is not constant, but depends on N, so you r right.

Complexity = $O(N.2^{N})$

---

@Kapil  SIR  , 

I have got one more doubt here . What IF the inner loop depends on outer loop ? What is the change in complexity in such case ? that is  What happens if inner loop is 

 for( j=i; j<N; j++) 

Answer 3

No of times if block successfully executes,

$$\begin{align*} &= (\text{no of one digit subset})*1 \\ & \;\;\;+ (\text{no of two digit subset})*2 \\ & \;\;\;+ (\text{no of three digit subset})*3 \\ & \;\;\;+ ........... \\ & \;\;\;+ (\text{no of n digit subset})*n \\ &= \binom{n}{1}*1 + \binom{n}{2}*2 + \binom{n}{3}*3 + ........... + \binom{n}{n}*n \\ &=n.2^{n-1} \end{align*}$$ 

Comments

How many times the if successfully executes

when N=n=3  while putting a value of n=3 in "n*2^(n-1)" we get the number of time if executed successfully is 12  which is same as  { 1,2,12,3,13,23,123 } //while counting all

I am not getting how are you calculating this?

(no of one digit subset) *1 +(no of two digit subset) *2 +........(no of  n digit subset) * n

here one digit number is 3 e.g 1,2,3  in sequence {1,1,12,3,13,23,123 } 

Answer 4

    #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;
    }

1
2
12
3
13
23
123

Now,

() has left to right associative and has greater precedence than any other operator.Precedence_Table.htm

<< left to right precedence, & has right to left precedence

For i=1

     and for j=0

  if((1<<j)&i)//1 will left shift 0 bit ,i.e.001+001=001

     So, if becomes true for j=0, in 1st iteration

     Prints 1

    for j=1

  if((1<<j)&i)//1 will left shift 1 bit ,i.e.010+001=000

    So, not executed

    for j=2

  if((1<<j)&i)//1 will left shift 2 bit ,i.e.100+001=000

    So, Not executed

for i=2

only

   for j=1

 if((1<<j)&i)//1 will left shift 1 bit ,i.e.010+010=010

    So,  executed a[j]=a[1]=2  Prints 2

for i=3

and for j=0

  if((1<<j)&i)//1 will left shift 0 bit ,i.e.001+001=001

     So, if becomes true for j=0, in 1st iteration

     Prints 1

  

for j=1

 if((1<<j)&i)//1 will left shift 1 bit ,i.e.010+010=010

    So,  executed a[j]=a[1]=2

    Prints 2

So, print 1 2

Likewise it will print.

Complexity will be $O(N(2^N-1))$=$O(N2^N)$

Comments

This is general case of  generating all combinations of a set using bit_masking. very useful for small n.