xCanaan xCanaan - 1 month ago 8
C Question

Can't Count - Number of Comparison Operations

So I have this segment of code that was given to me.

for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++)
{
if (arr[j] < arr[i])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}


I am trying to calculate the number of comparison operations that would occur if the code were to run.

There's the initial comparison all the way up to i=100. so there's 101 comparisons for the outer loop. The inner loop also has 101 loops, but that comparison within will only happen 100 times due to the j=100 will not have that comparison occurring.

I've made a tries but none of been the right answer so far.

I've had 101 x (101+100) = 20301 which is not the right answer.

I've searched for this on google and came up with a question identical to this but was answering how many assignment operations that occur which I was able to answer on my own. Which btw is 25201.

jxh jxh
Answer

100 comparisons on the outer loop drive 101 + 100 comparisons on the inner loop. There is one more comparison on the outer loop to detect loop termination, so:

100 * (101 + 100) + 101 = 20201.

Instrumenting the program:

outer_cmps=0;
total_inner_cmps=0;
for (int i = 0; i < 100; i++) {
   ++outer_cmps;
   inner_cmps=0;
   for (int j = 0; j < 100; j++) 
   {
     ++inner_cmps;
     if (arr[j] < arr[i]) 
     {
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
     }
     ++inner_cmps;
   }
   ++inner_cmps;
   tota_inner_cmps += inner_cmps;
}
++outer_cmps;
total_cmps = outer_cmps + total_inner_cmps;