Algorithm for check breakpoint for using sparse matrix

Question

I want to use sparse matrix or matrix, depending on efficiency and space saving

I’m trying to find what’s is more efficient and save space in run time

The size of the matrix is changing but every value is char (can be nothing -‘\0’)

I’m reading the data of the matrix values from file...

(In the beginning of each file there is the size of the matrix)

Thank you in advance

Answer 1

You can think on this as a graph representation. As you know, if you use matrix, the space complexity would be |V|^2 (|V| is number of nodes). Moreover, if you use adjacency matrix (or sparse matrix) the space complexity would be |V||E|, which |E| is the number of non-zero strings which are related to a node.

Hence, you can traverse the file and compare |V|^2 and |V||E| and decide base on these two values.