chap algorithm analysis the analysis techniques used to measure space requirements are similar to those used to measure time requirements howeverwhile time requirements are normally measured for an algorithm that manipulates particular data structurespace requirements are normally determined for the data structure itself the concepts of asymptotic analysis for growth rates on input size apply completely to measuring space requirements example what are the space requirements for an array of integersif each integer requires bytesthen the array requires cn byteswhich is th(nexample imagine that we want to keep track of friendships between people we can do this with an array of size each row of the array represents the friends of an individualwith the columns indicating who has that individual as friend for exampleif person is friend of person ithen we place mark in column of row in the array likewisewe should also place mark in column of row if we assume that friendship works both ways for peoplethe total size of the array is th( data structure' primary purpose is to store data in way that allows efficient access to those data to provide efficient accessit may be necessary to store additional information about where the data are within the data structure for exampleeach node of linked list must store pointer to the next value on the list all such information stored in addition to the actual data values is referred to as overhead ideallyoverhead should be kept to minimum while allowing maximum access the need to maintain balance between these opposing goals is what makes the study of data structures so interesting one important aspect of algorithm design is referred to as the space/time tradeoff principle the space/time tradeoff principle says that one can often achieve reduction in time if one is willing to sacrifice space or vice versa many programs can be modified to reduce storage requirements by "packingor encoding information "unpackingor decoding the information requires additional time thusthe resulting program uses less space but runs slower converselymany programs can be modified to pre-store results or reorganize information to allow faster running time at the expense of greater storage requirements typicallysuch changes in time and space are both by constant factor