Number of Comparisons

Question

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 n is the size of array A[ ] and starting index is 1)
Number of comparison made by the above code when n = 84 ________.

 

given answer is 84*83/2 =3486

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

Comments

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

---

when j=1, shouldnt k run 83-2+1= 82 times??

---

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]) ??

 

 

---

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

so answer should be (n-1)(n-2)/2

83*82/2= 3403

---

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 Shaik Masthan

 

---

According  to question feel it seems to get  A[j] > A[k] comparison. but if e go on language we need to calculate all .

---

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