algorithm analysis efficiency analysis to evaluate the various operations of the sparse matrixwe can assume square matrix since this would be the worst possible case we begin with the findposition(helper methodwhich performs sequential search over the list of non-zero entries the worst case occurs when every item in the list is examined but how many iterations does that requireit depends on the size of the element list from the definition of sparse matrixwe know it contains non-zero elements such that thusthe worst case run time of the helper method is (kthe setitem method calls findposition()which requires time it then changes the value of the target entrywhich is constant time operationor either removes an entry from the list or appends new entry the list operations require time in the worst caseresulting in an overall time of (kfor the set operation the getitem method can be evaluated in the same fashion and also has worst case time of (kto evaluate the operations that manipulate two sparsematrix objectswe can specify that both matrices are of the same size or that will represent the size of the larger of the two lists computing the worst case time for the new add(method requires that we first determine the complexity of the individual steps the size verification and new matrix creation are constant steps to duplicate the entries of the lefthand side sparse matrix requires time since append(has an amortized cost of ( the second loop iterates over the element list of the righthand side matrixwhich we have assumed also contains elements since the get and set element operations used within the loop each require time in the worst casethe loop requires or time combining this with the time for the previous stepsthe add operation is ( in the worst case is this time better than that for the add operation from the matrix class implemented as - arraythat depends on the size of if there were no zero elements in either matrixthen which results in worst case time of ( rememberhoweverthis implementation is meant to be used with sparse matrix in which in additionthe add operation only depends on the size of the element listk increasing the value of or does not increase the size of for the analysis of this algorithmm and simply provide maximum value for and are not variables in the equation the use of list as the underlying data structure to store the non-zero elements of sparse matrix is much better implementation than the use of - array as it can save significant storage space for large matrices on the other handit introduces element access operations that are more inefficient than when using the - array table provides comparison of the worst case time-complexities for several of the operations of the matrix class using - array and the sparsematrix class using list in later we will further explore the sparse matrix adt and attempt to improve the time-complexities of the various operations