The following questions are related to the Sparse Matrix ADT.
(a) Implement the remaining methods of the SparseMatrix class presented in the chapter using the array of sorted linked lists: getitem , transpose(), sub , and mul .
(b) Determine the time-complexity for each of the SparseMatrix methods implemented in part (a).
(c) Prove or show that the matrix addition operation of the SparseMatrix class, as implemented in the chapter using an array of sorted linked lists, has a worst case run time of O(kn).
(d) As you proved in part (c), the implementation of the SparseMatrix add method presented in the chapter is O(kn). A more efficient implementation is possible without the use of the getitem and setitem methods. Design and implement a new version of the add method that has a run time of no more than O(k).
(e) Show that your implementation of the add method from part(c) has a worst case run time of O(k).
(f) What advantages are there to using sorted linked lists with the Sparse Matrix ADT instead of unsorted linked lists?