Amortized analysis is an analysis technique that provides tight bounds on the worst-case running time of an algorithm that involves a sequence of possibly different operations. For example, suppose an algorithm used operations A, B, and C and applied them n times to a given data structure to transform it into a new data structure. For each of the n-applications, the algorithm chooses A, or B, or C. Further suppose that A and B run in constant time, O(1), whereas C is linear, or O(k), where k is some measure of the size of the data structure. A naive analysis of the running time of this algorithm would have to conclude that the running time is O(k*n) since in the worst possible scenario the algorithm would apply a O(k) operation n separate times. However, for many reasons, such a bound would not...