complexity of generating a sparse matrix


Keywords:r 


Question: 

I have a symmetric matrix S(n*n) where approximately 70% of the data are 0.

Symmetric matrix

enter image description here

I want to convert the symmetric matrix into a sparse matrix with t rows.

What would be the time complexity of generating a sparse matrix from the original symmetric matrix?

Is it O(n^2), because I have to go through every row/column intersection and get the elements that are not 0?

Since I am dealing with a symmetric matrix, can I can say that my time complexity could reduce to O((n*(n+1))/2) because in symmetric matrix a[i][j]= a[j][i]? In this case I could say a[j][i]=0 if I encounter a[i][j] as 0. This could reduce my loops by approximately half.


1 Answer: 

When converting from a full representation of a symmetric matrix to a sparse representation, you will need to scan all the elements on the main diagonal and above (or symmetrically on the main diagonal and below). For an (n x n) matrix matrix this is (n^2+n)/2 entries that need to be scanned. Therefore you need to perform O(n^2) work just to determine what needs to be inputted into the sparse matrix.

When constructing the sparse matrix, you will need to store all the non-empty entries in the original matrix into your sparse matrix. For a 0 matrix this requires no additional work and for a fully dense matrix this requires (n^2+n)/2 insertion operations.

Therefore converting from a symmetric matrix to a sparse representation will always take O(n^2) time -- in fact it takes Theta(n^2) time.