Question

Consider the program given below:

procedure mystery (int A[1 to 100])
int i, j, position, tmp;
begin
for j = 1 to 100 do
position = j;
for i = j to 100 do
if (A[i] > A [position]) then
position = i;
end for
tmp = A[j];
A[j] = A[position];
A[position] = tmp;
end for
end

Then, the number of times the test A[i] > A [position] is executed is

• A. 10000
• B. 5050
• C. 100
• D. Depends on contents of A

Answer 1

The correct option is B 5050

Option (b)
In iteration j, there are 100 -j + 1 comparisons made.

So, in all there are:
100 + 99 + ... + 2 + 1 = 5050