The Gateway to Computer Science Excellence
0 votes
45 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$
in Programming by Boss (16.8k points)
recategorized by | 45 views
0
It may look like the question is the part of CMI2019-A-9 question otherwise the code for above question is missing

2 Answers

0 votes
by (165 points)
0 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

 

 

    

ago by (73 points)
edited ago by

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,647 questions
56,459 answers
195,378 comments
100,276 users