recategorized by
607 views
1 votes
1 votes

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 by

3 Answers

1 votes
1 votes

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.

Answer is B

 

 

    

Answer:

Related questions

2 votes
2 votes
3 answers
2
1 votes
1 votes
2 answers
3
5 votes
5 votes
4 answers
4
gatecse asked Sep 13, 2019
2,331 views
Suppose that the figure to the right is a binary search tree. The letters indicate the names of the nodes, not the values that are stored. What is the predecessor node, i...