Time Complexity of Adding Three Matrices

What is the time complexity of adding three matrices of size NXN cell-by-cell?

Questions by govindarajmk

Showing Answers 1 - 15 of 15 Answers

stealth

  • Mar 2nd, 2010
 

The number of elements to be added is calculated in this way;

Total Number of Elements to be added  = No. of pairs of matrix * ( no. of elements in each matrix)

for 3 matrix; it would come to ; total number of operations required =

(n*n) * 2 ( as there are 2 add operations , m1 + m2 + m3) ~= O(2*(n^2))

For large number of n; it would be O(N^2)

Time complexity will be O(n^2), because if we add all the elements one by one to other matrics we have to traverse the whole matrix at least 1 time and traversion takes O(n^2) times. With this traversion we add 3 elements of location [i,j] and storing the result on other matrix at [i,j] location.

program looks like......

for(i=0;i<n;i++)
{
 for(j=0;j<n;j++)
 {
   result[i][j]=a[i][j]+b[i][j]+c[i][j];
 }
}

loop will execute n*n times...
and 2 add operations..
if 1 add op takes 'c' time, then
total time= 2*c*n*n
thus, time complexity= n*n......

  Was this answer useful?  Yes

Manish Yadav

  • Oct 15th, 2011
 

Time Complexity of Adding Three Matrices because there is only two loop are needed for adding the matrix

so complexity will be o(n^2), there is no effect for increase the number of matrix.

it will be same for n number of matrix.

Code
  1. algo like this.......

  2.  

  3. for(i=0;i<n;i++)

  4. {

  5.  for(j=0;j<n;j++)

  6.  {

  7.    result[i][j]=a[i][j]+b[i][j]+c[i][j]+...........................z[i][j];

  8.  }

  9. }

  10.  

  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions

 

Related Open Questions