amortized cost the append(operation of the list structure introduces special case in algorithm analysis the time required depends on the available capacity of the underlying array used to implement the list if there are available slotsa value can be appended to the list in constant time if the array has to be expanded to make room for the new valuehoweverthe append operation takes linear time when the array is expandedextra capacity is added that can be used to add more items without having to immediately expand the array thusthe number of times the append(operation actually requires linear time in sequence of operations depends on the strategy used to expand the underlying array consider the problem in which sequence of append operations are performed on an initially empty listwhere is power of list(for in range + appendi suppose the array is doubled in capacity each time it has to be expanded and assume the size of the underlying array for an empty list has the capacity for single item we can tally or compute the total running time for this problem by considering the time required for each individual append operation this approach is known as the aggregate method since it computes the total from the individual operations table illustrates the aggregate method when applied to sequence of append operations si represents the time required to physically store the ith value when there is an available slot in the array or immediately after the array has been expanded storing an item into an array element is constant time operation ei represents the time required to expand the array when it does not contain available capacity to store the item based on our assumptions related to the size of the arrayan expansion only occurs when is power of and the time incurred is based on the current size of the array ( while every append operation entails storage costrelatively few require an expansion cost note that as the size of increasesthe distance between append operations requiring an expansion also increases based on the tabulated results in table the total time required to perform sequence of append operations on an initially empty list is or just under this results from total storage cost (si of and total expansion cost (ei of it can be shown that for any nthe sum of the storage and expansion costssi ei will never be more than ( since there are relatively few expansion operationsthe expansion cost can be distributed across the sequence of operationsresulting in an amortized cost of ( / or ( for the append operation amortized analysis is the process of computing the time-complexity for sequence of operations by computing the average cost over the entire sequence for this technique to be appliedthe cost per operation must be known and it must