The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
109 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 ________.

 

given answer is 84*83/2 =3486

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

in Programming by (75 points)
edited by | 109 views
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

so answer should be (n-1)(n-2)/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

Please log in or register to answer this question.

Related questions

0 votes
0 answers
6
asked Dec 5, 2017 in Programming by Parshu gate Active (3.1k points) | 75 views
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,339 questions
55,763 answers
192,339 comments
90,774 users