Not getting what you are saying.

Are you saying this {1,2,3,4,5,6,7,8,9....................} ?

5 votes

#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.

1

If N=n, then array will be like {1,2,3,0,0,0,0,0,0,0,...........}

Not getting what you are saying.

Are you saying this {1,2,3,4,5,6,7,8,9....................} ?

Not getting what you are saying.

Are you saying this {1,2,3,4,5,6,7,8,9....................} ?

0

#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

1

#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.`

6 votes

Best answer

6 votes

**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)

0

@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

0

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})$

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})$

0

@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++)

4 votes

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*}$$

0

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 }

4 votes

#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)$