Data Structures, Algorithms, & Applications in C++
Chapter 7, Exercise 39

(a)

We shall ignore the space overheads of the array of arrays representation used by C++ and consider only the space for the 250000 elements in the 500 x 500 array. At 4 bytes per element, this works out to 1000000 bytes.

When a sparseMatrix is used, we need 12 bytes for each nonzero element. So, the 2000 nonzero element matrix takes 24000 bytes.

(b)

Using the same assumptions as in (a), 4mn bytes are taken by the two-dimensional array representation and 12p (p is the number of nonzero terms) by the sparse matrix representation. The sparse matrix representation takes more space when p > mn/3.