xCanaan - 9 months ago 37

C Question

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

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.

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;
```

Source (Stackoverflow)