Amortized analysis
In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case run time can be too pessimistic. Instead, amortized analysis averages the running times of operations in a sequence over that sequence. As a conclusion: “Amortized analysis is a useful tool that complements other techniques such as worst-case and average-case analysis.“ For a given operation of an algorithm, certain situations (e.g., input parametrizations or data structure  contents) may imply a significant cost in resources, whereas other situations may not be as costly. The amortized analysis considers both the costly and less costly operations together over the whole sequence of operations. This may include accounting for different types of input, length of the input, and other factors that affect its performance. History. Amortized analysis initially emerged from a method called aggregate analysis, which is now subsumed by amortized analysis. The technique was first formally introduced by Robert Tarjan in his 1985 paper "Amortized Computational Complexity", which addressed the need for a more useful form of analysis than  the common probabilistic methods used. Amortization was initially used for very specific types of algorithms, particularly those involving binary trees and union operations. However, it is now ubiquitous and comes into play when analyzing many other algorithms as well. Method. Amortized analysis requires knowledge of which series of operations are possible. This is most commonly the case with data structures, which have state that persists between operations. The basic idea is that a worst-case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost . There are generally three methods for performing amortized analysis: the aggregate method, the accounting method, and the potential method. All of these give correct answers; the choice of which to use depends on which is most convenient for a particular situation. Examples. Dynamic array. Consider a dynamic array that grows in size as more elements are added to it, such as in Java or in C++. If we started out with a dynamic array of size 4, we could push 4 elements onto it, and each operation would take constant time. Yet pushing a fifth element onto that array would  take longer as the array would have to create a new array of double the current size (8), copy the old elements onto the new array, and then add the new element. The next three push operations would similarly take constant time, and then the subsequent addition would require another slow doubling of the array size. In general if we consider an arbitrary number of pushes "n" + 1 to an array of size "n", we notice that push operations take constant time except for the last one which takes time to perform the size doubling operation. Since there were  n + 1 operations total we can take the average of this and find that pushing elements onto the dynamic array takes: formula_1, constant time. Queue. Shown is a Ruby implementation of a Queue, a FIFO data structure: class Queue end The enqueue operation just pushes an element onto the input array; this operation does not depend on the lengths of either input or output and therefore runs in constant time. However the dequeue operation is more complicated. If the output array already has some elements in it, then dequeue runs in constant time; otherwise, dequeue takes time to add  all the elements onto the output array from the input array, where "n" is the current length of the input array. After copying "n" elements from input, we can perform "n" dequeue operations, each taking constant time, before the output array is empty again. Thus, we can perform a sequence of "n" dequeue operations in only time, which implies that the amortized time of each dequeue operation is . Alternatively, we can charge the cost of copying any item from the input array to the output array to the earlier enqueue operation for that item. This charging scheme doubles the amortized  time for enqueue but reduces the amortized time for dequeue to .