amortized analysis this section presents the concept of amortized analysiswhich is the analysis for series of operations taken as whole in particularamortized analysis allows us to deal with the situation where the worst-case cost for operations is less than times the worst-case cost of any one operation rather than focusing on the individual cost of each operation independently and summing themamortized analysis looks at the cost of the entire series and "chargeseach individual operation with share of the total cost we can apply the technique of amortized analysis in the case of series of sequential searches in an unsorted array for random searchesthe average-case cost for each search is / and so the expected total cost for the series is / unfortunatelyin the worst case all of the searches would be to the last item in the array in this caseeach search costs for total worst-case cost of compare this to the cost for series of searches such that each item in the array is searched for precisely once in this situationsome of the searches must be expensivebut also some searches must be cheap the total number in the bestavpn of searches erageand worst casefor this problem must be = / this is factor of two better than the more pessimistic analysis that charges each operation in the series with its worst-case cost as another example of amortized analysisconsider the process of incrementing binary counter the algorithm is to move from the lower-order (rightmostbit toward the high-order (leftmostbitchanging to until the first is encountered this is changed to and the increment operation is done below is java code to implement the increment operationassuming that binary number of length is stored in array of length for ( = (( < length&( [ = )) ++ [ if ( lengtha[ if we count from through (requiring counter with at least bits)what is the average cost for an increment operation in terms of the number of bits processednaive worst-case analysis says that if all bits are (except for the high-order bit)then bits need to be processed thusif there are incrementsthen the cost is howeverthis is much too highbecause it is rare for so many bits to be processed in facthalf of the time the low-order bit is and so only that bit is processed one quarter of the timethe low-order two bits are and so only the low-order two bits are processed another way to view this is that the low-order bit is always flippedthe bit to its left is flipped half the timethe next