xCanaan - 1 year ago 60
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.

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;
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download