Please, can anyone help with this question? It\'s a C++ data structure question

Question

Please, can anyone help with this question? It's a C++ data structure question from one of the books. The topic is about "Time Complexity"

Thank you. Much appreciated.

Question 1: (a) Give a quick approximation of the operation count and 00 for function F below, where n is the size of the input. Justif our answer. (2 marks void F (int hs, int rhs, int **res, int n) for (int i E 0; i n, i++) for (int j 0; j n; j++) int sum 0; for (int k 1; k n-1: k++) sum lhs [i][k] rhs [klU1; Y res [i]U] sum; (b) Derive the exact operation count for the above function F, showing all necessary details of your calculation. Give the OC accordingly. (2 marks)

Explanation / Answer

a)

void F(int **lhs, int **rhs, int **res, int n) {
   for(int i=0; i<n; i++) {
       for(int j=0; j<n; j++) {
           int sum = 0;
           for(int k=1; k<n-1; k++) {
               sum += lhs[i][k] * rhs[k][j];
           }
           res[i][j] = sum;
       }
   }
}

Lets try to calculate the operation count.

So Outer loop of variable i, runs for n times. Similarly, mid loop of variable j, runs for n times. The innermost loop runs for (n-2) times. So overall complexity is meansured by multiplying all these three.

It will be n * n * (n-2). Or if we talk in Upper bound or Big O complexity, It will be roughly O(N^3)

Part B). The exact count i have given above. It will be N * N * (N - 2).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---