proposition let be sequence implemented by means of dynamic array with initial capacity oneusing the strategy of doubling the array size when full the total time to perform series of append operations in sstarting from being emptyis (njustificationlet us assume that one cyber-dollar is enough to pay for the execution of each append operation in sexcluding the time spent for growing the array alsolet us assume that growing the array from size to size requires cyberdollars for the time spent initializing the new array we shall charge each append operation three cyber-dollars thuswe overcharge each append operation that does not cause an overflow by two cyber-dollars think of the two cyber-dollars profited in an insertion that does not grow the array as being "storedwith the cell in which the element was inserted an overflow occurs when the array has elementsfor some integer > and the size of the array used by the array representing is thusdoubling the size of the array will require cyber-dollars fortunatelythese cyber-dollars can be found stored in cells - through (see figure note that the previous overflow occurred when the number of elements became larger than - for the first timeand thus the cyber-dollars stored in cells - through have not yet been spent thereforewe have valid amortization scheme in which each operation is charged three cyber-dollars and all the computing time is paid for that iswe can pay for the execution of append operations using cyber-dollars in other wordsthe amortized running time of each append operation is ( )hencethe total running time of append operations is ( ( ( figure illustration of series of append operations on dynamic array(aan -cell array is fullwith two cyber-dollars "storedat cells through (ban append operation causes an overflow and doubling of capacity copying the eight old elements to the new array is paid for by the cyber-dollars already stored in the table inserting the new element is paid for by one of the cyber-dollars charged to the current append operationand the two cyber-dollars profited are stored at cell