The Gateway to Computer Science Excellence
0 votes

Consider the following code segment:

int j, k,n;



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





(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 | 120 views
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


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

Please log in or register to answer this question.

Related questions

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,737 questions
57,281 answers
104,842 users