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:
- $4950$
- $5050$
- $10000$
- Depends on the contents of $A$