# Number of Comparisons

173 views

Consider the following code segment:

int j, k,n;

for(j=1;j<=n-1;j++){

for(k=j+1;k<n;k++){

if(A[j]> A[k]){

A[j]=A[j+2];

}

}

}

(Where is the size of array A[ ] and starting index is 1)
Number of comparison made by the above code when = 84 ________.

shouldn’t it be 83*82/2 = 3403

edited
0
no it will be (n* n+1) /2

when j=1 k runs 83

when j=2 k runs 82 times

similarly when j=83 k runs 0 times

so totally 83+82+81+...1+0 ==> (83*84)/2  => we can correlate this like 1+2+3+4 = 10 i.e. (4*5)/2
0
when j=1, shouldnt k run 83-2+1= 82 times??
0

are u speaking about the comparisons of the inner for loop or the comparison  that is being performed inside the loop, i.e. (A[j]> A[k]) ??

1
Yes sorry my mistake. yes it will run 83*82/2 times

if we take n=5

then j= 1,2,3,4

j=1 k=2,3,4

j=2 k=3,4

j=3 k=4

j=4 k no loop

total= 3+2+1 =6 =4*3/2

83*82/2= 3403
0

I guess that we shouldnt consider only the comparisons performed by A[j]> A[k] .

What about the comparisons made in the inner and outer for loops?shouldnt we consider them too?

pls verify

0
According  to question feel it seems to get  A[j] > A[k] comparison. but if e go on language we need to calculate all .
0
I think, if we consider comparison in for loops, then it will be more than 84*83/2 =3486

with only considering comparison within for loops then answers will be  83*82/2 = 3403

## Related questions

1
929 views
What is the return value of following function for 484? What does it to in general? bool fun(int n) { int sum = 0; for (int odd = 1; n > sum; odd = odd+2) sum = sum + odd; return (n == sum); } (A) False, it checks whether a given number is ... , it checks whether a given number is odd or not (D) True, it checks whether a given number is perfect square. Any one can explain output of above program?
1 vote