analysis techniques this book contains many examples of asymptotic analysis of the time requirements for algorithms and the space requirements for data structures often it is easy to invent an equation to model the behavior of the algorithm or data structure in questionand also easy to derive closed-form solution for the equation should it contain recurrence or summation sometimes an analysis proves more difficult it may take clever insight to derive the right modelsuch as the snowplow argument for analyzing the average run length resulting from replacement selection (section in this caseonce the snowplow argument is understoodthe resulting equations are simple sometimesdeveloping the model is straightforward but analyzing the resulting equations is not an example is the average-case analysis for quicksort the equation given in section simply enumerates all possible cases for the pivot positionsumming corresponding costs for the recursive calls to quicksort howeverderiving closed-form solution for the resulting recurrence relation is not as easy many iterative algorithms require that we compute summation to determine the cost of loop techniques for finding closed-form solutions to summations are presented in section time requirements for many algorithms based on recursion are best modeled by recurrence relations discussion of techniques for solving recurrences is provided in section these sections extend the introduction to summations and recurrences provided in section so the reader should already be familiar with that material section provides an introduction to the topic of amortized analysis amortized analysis deals with the cost of series of operations perhaps single operation in the series has high costbut as result the cost of the remaining operations is limited in such way that the entire series can be done efficiently amortized analysis has been used successfully to analyze several of the algorithms presented in