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$

recategorized | 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

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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.71292835,"math_prob":0.9993598,"size":620,"snap":"2019-51-2020-05","text_gpt3_token_len":246,"char_repetition_ratio":0.09902597,"word_repetition_ratio":0.0,"special_character_ratio":0.47741935,"punctuation_ratio":0.25139666,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99963176,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-12-07T20:38:22Z\",\"WARC-Record-ID\":\"<urn:uuid:3eafc50e-b012-4508-820b-903102c43009>\",\"Content-Length\":\"75880\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:407d25e6-a9f8-48c7-ac72-4b306963f0fa>\",\"WARC-Concurrent-To\":\"<urn:uuid:0491f71c-53c4-47f7-97ce-0dc039584328>\",\"WARC-IP-Address\":\"104.27.188.78\",\"WARC-Target-URI\":\"https://gateoverflow.in/320544/cmi2019-a-10\",\"WARC-Payload-Digest\":\"sha1:CAKJPX5WAN6VX4V2ZSGYYAAEGH3T73E5\",\"WARC-Block-Digest\":\"sha1:KCIJ642ER56JMB4VYR2DPWXODNQ2WRRG\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-51/CC-MAIN-2019-51_segments_1575540501887.27_warc_CC-MAIN-20191207183439-20191207211439-00085.warc.gz\"}"}