chap analysis techniques bit one quarter of the timeand so on we can capture this with the summation (charging costs to bits going from right to leftn- = in other wordsthe average number of bits flipped on each increment is leading to total cost of only for series of increments useful concept for amortized analysis is illustrated by simple variation on the stack data structurewhere the pop function is slightly modified to take second parameter indicating that pop operations are to be performed this revised pop functioncalled multipopmight look as follows/pop elements from stack void multipop(int )the "localworst-case analysis for multipop is th(nfor elements in the stack thusif there are calls to push and calls to multipopthen the naive worst-case cost for the series of operation is this analysis is unreasonably pessimistic clearly it is not really possible to pop elements each time multipop is called analysis that focuses on single operations cannot deal with this global limitand so we turn to amortized analysis to model the entire series of operations the key to an amortized analysis of this problem lies in the concept of potential at any given timea certain number of items may be on the stack the cost for multipop can be no more than this number of items each call to push places another item on the stackwhich can be removed by only single multipop operation thuseach call to push raises the potential of the stack by one item the sum of costs for all calls to multipop can never be more than the total potential of the stack (aside from constant time cost associated with each call to multipop itselfthe amortized cost for any series of push and multipop operations is the sum of three costs firsteach of the push operations takes constant time secondeach multipop operation takes constant time in overheadregardless of the number of items popped on that call finallywe count the sum of the potentials expended by all multipop operationswhich is at most the number of push operations this total cost can therefore be expressed as ( th(