80 views

The next two questions refer to the following program.

In the code below reverse$(A,i,j)$ takes an array $A,$ indices $i$ and $j$ with $i\leq j,$ and reverses the segment $A[i],A[i+1],\cdots,A[j].$ For instance if $A=[0,1,2,3,4,5,6,7]$ then, after we apply reverse$(A,3,6),$ the contents of the array will be $A=[0,1,2,6,5,4,3,7].$

function mystery (A[0...99]) {
int i, j, m;
for (i = 0; i < 100; i++) {
m = i;
for (j = i; j < 100; j++) {
if (A[j] > A[m]) {
m = j;
}
}
reverse(A,i,m);
}
return;
}

The number of times the test $A[ j ] > A[ m ]$ is executed is:

1. $4950$
2. $5050$
3. $10000$
4. Depends on the contents of $A$

recategorized | 80 views
0
It may look like the question is the part of CMI2019-A-9 question otherwise the code for above question is missing

by (165 points)

There are total two loops , No of time inner loop execution depends on outer loop counter value ( 'i' value).

Basically

i=0 , inner loop will execute 100 times    (n times)

i=1, inner loop will execute 99 times       ( 'n-1' times)

i=2 , inner loop will execute 98 times      ( 'n-2' times)

.

.

.

i=99, inner loop will execute 1    ( 1 time )

A[j]>A[m]  this condition checks inside inner loop every time , so total number of inner loop execution is equal to total number of time this comparison executes.

Total number inner loop execution = n+(n-1)+(n-2)+. . . . . +1

= n(n+1)/2                                   ( sum of first N natural numbers)

In above program value of 'i' is start from 0 and reach till 99 (total 100 times)  , it's not depend on number of element in array A.

Now put n=100

total execution = 100 (100+1)/2

=5050 times.

by (147 points)
edited