# Time complexity and output

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

retagged
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....................} ?
1
no no..:) calculate it for given program ...then generalize for N = n
1
For N = n, the IF block executes $2^{n} - 1$
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

0
Yes, that is good otherwise needed to count as it grows polynomially.
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.

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

selected by

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)

edited by
1
• it is growing exponentially.
• To print $123$ , control enters inside if block three times
0
Yes, for 123 three times ,i.e respectively for every j.
0

can u explain how does

(1<<j)&i)


works ?

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

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 }

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

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

## Related questions

1 vote
1
137 views
The following sum of $n+1$ terms $2 + 3 \times \begin{pmatrix} n \\ 1 \end{pmatrix} + 5 \times \begin{pmatrix} n \\ 2 \end{pmatrix} + 9 \times \begin{pmatrix} n \\ 3 \end{pmatrix} + 17 \times \begin{pmatrix} n \\ 4 \end{pmatrix} + \cdots$ up to $n+1$ terms is equal to $3^{n+1}+2^{n+1}$ $3^n \times 2^n$ $3^n + 2^n$ $2 \times 3^n$
int main() { int n = 3,i,count=0; for(i=0;i<1<<n;i++) { int p = i; while(p) { int k = p & -p; p = p - k; count++; } } } The value of count variable after execution of the above code? The value of count variable when $n = m$ ? [EDITED]