Counting total number of arithmetic operations in nested loop

lost110 (140)
Hello! So here is a question. I have to count the number of arithmetic operations when given an array to sort A(4,2,5,3,1). SO N=5
So I am just trying to figure it out through these nested loops.

i =1 : 1 time
i < n-1 : 4 time
i++ : 5 times

operation 1+4+5 = 10

Same with the second loop
operations in second loop = 10

So overall 10 + 10 + 9= 29 arithmetic operations.
I am not sure about if(A[j] > A(j+1)). Will they count? 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
 Fastsort(A.n)
{
  for( i = 1 ; i < n-1 ; i++)
 {
   for( j = 0 ; j < n-1 ; j++)
  {
    if(A[j] > A(j+1))
    {
       swap (A[j] < A[j+1])// this function needs no improvement and uses 9 
                                                                 operations
    }
   }
 }
}
dutch (2548)
Besides being horribly misnamed, the algorithm is wrong since the outer loop needs to go n times, not n - 1 times. So it's either for(i = 1; i < n; ++i) or for(i = 0; i < n-1; ++i)

With that correction, here's the operation counts:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
Fastsort(A, n)
{
  //     1      5      4
  for (i = 1; i < n; i++)
  {
    //     4     20       16
    for (j = 0; j < n-1; j++)
    {
      //      16
      if (A[j] > A[j+1])
      {
        swap(A[j], A[j+1])  // perhaps 8 * 9 = 72
      }
    }
  }
}

So that's a total of 66 ops without counting swap. If we need to count the "9 operations" in the swap function then we could assume it runs about half the time, so (16/2)*9 = 72 and 66 + 72 = 138 operations.
markyrocks (346)
there's always room for improvement. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 

#include <iostream>
#include<algorithm>
using namespace std;


int main() {
	int a[] = { 4,2,5,3,1 };

	for (int i = 0; i<5; i++) {
		auto min = min_element(begin(a) + i, end(a));
		iter_swap(begin(a) + i, min);
	}

	for (int i = 0; i < 5; i++) {
		cout << a[i] << "\n";
	}
}
dutch (2548)
there's always room for improvement

You're either joking or completely missed the point. :-)
markyrocks (346)
I guess it could look like this but not trying to get too fancy. 

1
2
3
4
5
 

for (auto i = begin(a); i<end(a); i++) { 	
iter_swap(i, min_element(i,end(a))); 
}


I realize that the min_element function is doing comparisons they can be counted. Untested but it looks OK on my phone. I bet mine is less.
Last edited on
lost110 (140)
@dutch
Is the below count correct if i =0?
1
2
3
4
5
 
Fastsort(A, n)
{
  //     1          4         4
  for (i = 0; i < n-1; i++)

But I read somewhere that the condition operation (i<n-1) should run 1 time more than the increment operation(i++). So won't it be 
1
2
3
4
 
 
//     1          4         3
    for (i = 0; i < n-1; i++)

Last edited on
dutch (2548)
Yes, the test will run one more time than the increment, but if n is 5 then the counts would be:

1
2
3
4
 
Fastsort(A, n)
{
  //     1      5       4
  for (i = 0; i < n-1; i++)

The test occurs for i = 0, 1, 2, 3, 4.
When i is 4, the test will be false, but it is still executed.
Topic archived. No new replies allowed.