is member of set if the element is not member of set ait' added to set by applying the append(list method we know from earlier the linear search performed by the in operator requires (ntime and we can use the ( amortized cost of the append(method since it is applied in sequence given that the loop is performed times and each iteration requires timethis step requires ( time combining the times for the three steps yields worst case time of ( applicationthe sparse matrix matrix containing large number of zero elements is called sparse matrix sparse matrices are very common in scientific applicationsespecially those dealing with systems of linear equations sparse matrix is formally defined to be an mxn matrix that contains non-zero elements such that mxn the - array data structure used to implement the matrix adt in works well for general matrices but when used to store huge sparse matriceslarge amounts of memory can be wasted and the operations can be inefficient since the zero elements are also stored in the - array consider the sample sparse matrix in figure is there different structure or organization we can use to store the elements of sparse matrix that does not waste spaceone approach is to organize and store the non-zero elements of the matrix within single list instead of - array figure sample sparse matrix with zero elements indicated with dots list-based implementation in this sectionwe define and implement class for storing and working with sparse matrices in which the non-zero elements are stored in list the operations of sparse matrix are the same as those for general matrix and many of them can be implemented in similar fashion as was done for the matrix class in listing this would be sufficient if our only objective was to reduce the storage costbut we can take advantage of only storing the non-zero elements to improve the efficiency of several of the sparse matrix operations the implementation of the sparsematrix class is provided in listing on the next page note the use of the new class name to distinguish this version from the original matrix adt and to indicate it is meant for use with sparse matrices sample instance of the class that corresponds to the sparse matrix from figure is illustrated in figure