Amortized analysis

Method

Amortized analysis requires knowledge of which series of operations are possible. This is most commonly the case with data structures, which have a 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.

• Aggregate analysis determines the upper bound T(n) on the total cost of a sequence of n operations, then calculates the amortized cost to be T(n) / n.
• The accounting method is a form of aggregate analysis which assigns to each operation an amortized cost which may differ from its actual cost. Early operations have an amortized cost higher than their actual cost, which accumulates a saved "credit" that pays for later operations having an amortized cost lower than their actual cost. Because the credit begins at zero, the actual cost of a sequence of operations equals the amortized cost minus the accumulated credit. Because the credit is required to be non-negative, the amortized cost is an upper bound on the actual cost. Usually, many short-running operations accumulate such credit in small increments, while rare long-running operations decrease it drastically.
• The potential method is a form of the accounting method where the saved credit is computed as a function (the "potential") of the state of the data structure. The amortized cost is the immediate cost plus the change in potential.

Examples

Dynamic array

Consider a dynamic array that grows in size as more elements are added to it, such as ArrayList in Java or std::vector 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 a scaled size, copy the old elements onto the new array, then add the new element. The next few push operations would similarly take constant time, then the subsequent addition would require another slow scaling of the array size.

In general, for an arbitrary number ${\displaystyle n}$ of pushes to an array of any initial size, the times for steps that scale the array add in a geometric series to ${\displaystyle O(n)}$, while the constant times for each remaining push also add to ${\displaystyle O(n)}$. Therefore the average time per push operation is ${\displaystyle O(n)/n=O(1)}$. This reasoning can be formalized and generalized to more complicated data structures using amortized analysis.

Queue

Shown is a Python implementation of a queue, a FIFO data structure:

<span id="mwcQ"></span><span class="k" id="mwcg">class</span><span class="w" id="mwcw"> </span><span class="nc" id="mwdA">Queue</span><span class="p" id="mwdQ">:</span> <span class="w" id="mwdg"> </span><span class="sd" id="mwdw">"""Represents a first-in, first-out collection."""</span> <span class="c1" id="mweA"># Initialize the queue with two empty lists</span> <span class="k" id="mweQ">def</span><span class="w" id="mweg"> </span><span class="fm" id="mwew">__init__</span><span class="p" id="mwfA">(</span><span class="bp" id="mwfQ">self</span><span class="p" id="mwfg">):</span> <span class="bp" id="mwfw">self</span><span class="o" id="mwgA">.</span><span class="n" id="mwgQ">input</span> <span class="o" id="mwgg">=</span> <span class="p" id="mwgw">[]</span> <span class="c1" id="mwhA"># Stores elements that are enqueued</span> <span class="bp" id="mwhQ">self</span><span class="o" id="mwhg">.</span><span class="n" id="mwhw">output</span> <span class="o" id="mwiA">=</span> <span class="p" id="mwiQ">[]</span> <span class="c1" id="mwig"># Stores elements that are dequeued</span> <span class="k" id="mwiw">def</span><span class="w" id="mwjA"> </span><span class="nf" id="mwjQ">enqueue</span><span class="p" id="mwjg">(</span><span class="bp" id="mwjw">self</span><span class="p" id="mwkA">,</span> <span class="n" id="mwkQ">element</span><span class="p" id="mwkg">):</span> <span class="w" id="mwkw"> </span><span class="sd" id="mwlA">"""Add an object to the end of the queue."""</span> <span class="bp" id="mwlQ">self</span><span class="o" id="mwlg">.</span><span class="n" id="mwlw">input</span><span class="o" id="mwmA">.</span><span class="n" id="mwmQ">append</span><span class="p" id="mwmg">(</span><span class="n" id="mwmw">element</span><span class="p" id="mwnA">)</span> <span class="c1" id="mwnQ"># Append the element to the input list</span> <span class="k" id="mwng">def</span><span class="w" id="mwnw"> </span><span class="nf" id="mwoA">dequeue</span><span class="p" id="mwoQ">(</span><span class="bp" id="mwog">self</span><span class="p" id="mwow">):</span> <span class="w" id="mwpA"> </span><span class="sd" id="mwpQ">"""Remove and return the object at the beginning of the queue."""</span> <span class="k" id="mwpg">if</span> <span class="ow" id="mwpw">not</span> <span class="bp" id="mwqA">self</span><span class="o" id="mwqQ">.</span><span class="n" id="mwqg">output</span><span class="p" id="mwqw">:</span> <span class="c1" id="mwrA"># If the output list is empty</span> <span class="c1" id="mwrQ"># Transfer all elements from the input list to the output list, reversing the order</span> <span class="k" id="mwrg">while</span> <span class="bp" id="mwrw">self</span><span class="o" id="mwsA">.</span><span class="n" id="mwsQ">input</span><span class="p" id="mwsg">:</span> <span class="c1" id="mwsw"># While the input list is not empty</span> <span class="bp" id="mwtA">self</span><span class="o" id="mwtQ">.</span><span class="n" id="mwtg">output</span><span class="o" id="mwtw">.</span><span class="n" id="mwuA">append</span><span class="p" id="mwuQ">(</span> <span class="bp" id="mwug">self</span><span class="o" id="mwuw">.</span><span class="n" id="mwvA">input</span><span class="o" id="mwvQ">.</span><span class="n" id="mwvg">pop</span><span class="p" id="mwvw">()</span> <span class="p" id="mwwA">)</span> <span class="c1" id="mwwQ"># Pop the last element from the input list and append it to the output list</span> <span class="k" id="mwwg">return</span> <span class="bp" id="mwww">self</span><span class="o" id="mwxA">.</span><span class="n" id="mwxQ">output</span><span class="o" id="mwxg">.</span><span class="n" id="mwxw">pop</span><span class="p" id="mwyA">()</span> <span class="c1" id="mwyQ"># Pop and return the last element from the output list</span>

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 ⁠${\displaystyle O(n)}$⁠ 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 ⁠${\displaystyle O(n)}$⁠ time, which implies that the amortized time of each dequeue operation is ⁠${\displaystyle O(1)}$⁠.

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 ⁠${\displaystyle O(1)}$⁠.

Common use

• In common usage, an "amortized algorithm" is one that an amortized analysis has shown to perform well.
• Online algorithms commonly use amortized analysis.

Literature

• "Lecture 7: Amortized Analysis" (PDF). Carnegie Mellon University. Retrieved 14 March 2015.
• Allan Borodin and Ran El-Yaniv (1998). Online Computation and Competitive Analysis. pp. 20, 141.