Vrinda writes an efficient program to sum two square diagonal matrices (matrices with elements only on diagonal) the size of each matrix is nxn. what is the time complexity of vrinda's algorithm?
Answers
We know a square matrix can be a diagonal matrix.The number of diagonal elements in Square matrix of size n*n is n.
Diagonal matrix : A matrix having non zero elements diagonally.
therefore time complexity is O(n).
O(n^2) because to access 2-d array we have to run to for loops thus adding to nXn matrices will take O(n^2)
Answer:
Answer by TCIL-IT Chandigarh (ICS Group)
6 Weeks & Six Months Industrial Summer Training in Chandigarh Mohali Panchkula
In general when we have a normal 2-D square matrix of size NxN, we create 2 for loops the outer loop iterates over the rows of the matrix and the lower loop iterates over the columns of the matrix and we add the both.
But in this situation we are having a square diagonal matrix which has elements only in the diagonal in which each diagonal element has same the same row index and same column index.
For eg:
[[1 0 0],
[0 1 0],
[0 0 1 ]]
+
[[1 0 0],
[0 1 0],
[0 0 1 ]]
Now here we see we only have to iterate over the diagonal elements only so the time complexity is O(n).
Step-by-step explanation:
*Copy and paste the below code in the compiler and just change the class to Main
import java.util.*;
class TCIL_IT_CHANDIGARH_ICS_GROUP{
public static void main(String[] args){
int sum=0;
int j=0;
int N=3;
int[][] array1={{1,0,0},{0,1,0},{0,0,1}};
int[][] array2={{1,0,0},{0,1,0},{0,0,1}};
// The above two arrays are of shape NxN, here N=3
// The below array of same shape NxN has all elements as 0 and diagonal elements will be updated after doing sum of previous two arrays
// www.tcilitchandigarh.com
// www.icsitchandigarh.com
int[][] array3={{0,0,0},{0,0,0},{0,0,0}};
for(int i=0;i<N;i++)
{
sum=array1[i][j]+array2[i][j];
array3[i][j]=sum;
j++;
}
System.out.println("Solved by TCIL-IT CHANDIGARH (ICS GROUP) 6 Weeks & Six Months Industrial Summer Training Company in Chandigarh Mohali Chandigarh\n\nWe have just used a single loop for adding two squared diagonal elements\n\nThe thrid matrix after adding of previous two is below\n");
// We are printing the array3 having the sum of previous two squared diagonal arrays
for(int l=0;l<N;l++){
for(int k=0;k<N;k++){
System.out.print(array3[l][k]+" ");
}
System.out.println();
}
System.out.println("\nSolved by TCIL-IT CHANDIGARH (ICS GROUP)\n6 Weeks & Six Months Industrial Summer Training Company in Chandigarh Mohali Chandigarh");
}
}