Amortized Complexity
Prerequisite reading: time complexity
This page introduces the basics of amortized complexity.
Introduction
Amortized analysis is a technique for analyzing the performance of algorithms and dynamic data structures. Rather than looking only at the cost of a single operation, it evaluates the average cost over a sequence of operations, which gives a more accurate picture of overall performance. Amortized analysis involves no probability: it guarantees only the average time per operation in the worst case, and says nothing about the average-case performance of the system. In the worst case, it spreads the cost of expensive operations over cheap ones, so that the average cost per operation stays within a reasonable bound.
Amortized analysis is usually carried out with one of three main methods: aggregate analysis, the accounting method and the potential method. Each has its own emphasis and suits different situations, but all three aim to even out the costs of operations and thereby optimize the overall worst-case performance of a data structure.
Methods
Consider a growable array, such as vector in C++, with initial capacity \(m = 1\). Whenever a new element is inserted and the array is full, we double the size of the array, copy the elements of the old array into the new one, and then insert the new element.
Below we take insertion into a dynamic array as the example and analyze its amortized cost with each of the three methods: aggregate analysis, the accounting method and the potential method.
Aggregate analysis
Aggregate analysis computes the total cost of a sequence of operations and averages it over the operations, which gives the amortized time complexity of each operation.
For the dynamic array, start with the two key costs of an insertion:
- If the array is not full, the insertion costs \(O(1)\).
- If the array is full, the insertion has to resize it, and copying the elements after the resize costs \(O(m)\), where \(m\) is the current size of the array.
So the total cost of \(n\) insertions can be computed in two parts:
- Cost of the insertions: the direct cost of inserting each new element is constant, \(O(1)\), so over \(n\) operations the total is \(O(n)\).
- Cost of resizing the array: each resize copies the elements of the old array into the new one. This happens when the size of the array is a power of \(2\). The total number of elements copied in resizes is the sum of all powers of two strictly less than \(n\). For \(n\ge1\) the total copying cost is \(\sum_{i=0}^{\lceil\log_2 n\rceil - 1}2^i=2^{\lceil\log_2 n\rceil}-1<2n\), so the total is \(O(n)\).
So the total cost of the insertions into the array is \(O(n)\), which is \(O(1)\) amortized per operation. Even in the worst case, the average cost of an insertion is still constant.
Accounting method
The accounting method assigns each operation a fixed amortized cost in advance, in such a way that the total cost of all operations never exceeds the sum of these assigned costs. It works like a prepayment scheme: cheap operations store some credit, which later pays for expensive ones.
For the dynamic array, we can assign each insertion a fixed amortized cost that guarantees enough credit has been set aside by the time a resize is needed.
-
Assigning credit:
- Suppose each insertion has actual cost \(1\), and set its amortized cost to \(3\).
- Of this, \(1\) pays for the insertion itself and \(2\) is kept for a possible future resize.
-
Spending credit:
- When the array is full it has to be resized, at an actual cost of \(O(m)\), where \(m\) is the current size of the array.
- Suppose the array holds \(n\) elements before the resize. The \(n/2\) elements in the second half of the old array stored \(n\) units of amortized cost in total when they were inserted, which is exactly enough to pay for the resize.
Here is a concrete example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
This shows that the amortized cost stored by each insertion is enough to pay for future resizes, which keeps the amortized cost of every operation at \(O(1)\).
Potential method
The potential method defines a potential function (usually written \(\Phi\)) that measures the potential energy of a data structure: resources held in reserve in the state of the system, which can pay for expensive operations later. Changes in potential balance the total cost of a sequence of operations, which keeps the amortized cost of the whole algorithm within a reasonable bound.
How it works
First, define the state \(S\) to be the state of the data structure at some moment. It may include information such as the number of elements, the capacity and pointers. The initial state, before any operation has been performed, is \(S_0\).
Next, define a potential function \(\Phi(S)\) that measures the potential of the state \(S\) of the data structure. With \(S_0\) the initial state, the potential of every reachable state \(S\) must satisfy \(\Phi(S) \geq \Phi(S_0)\)123. Some sources additionally require \(\Phi(S_0)=0\)4, but this is not actually necessary.
The amortized cost \(\hat{c}\) of each operation is defined as
where \(c\) is the actual cost of the operation, and \(S\) and \(S'\) are the states of the data structure before and after it. The formula says that the amortized cost equals the actual cost plus the change in potential. If the operation increases the potential (\(\Phi(S') > \Phi(S)\)), the amortized cost goes up; if it uses up potential (\(\Phi(S') < \Phi(S)\)), the amortized cost goes down.
The potential function lets us analyze the total cost of a sequence of operations. Let \(S_1, S_2, \dots, S_m\) be the sequence of states produced by \(m\) operations starting from the initial state \(S_0\), and let \(c_i\) be the actual cost of the \(i\)-th operation. Then the amortized cost \(p_i\) of the \(i\)-th operation is
So the total time spent on the \(m\) operations is
Since \(\Phi(S) \geq \Phi(S_0)\), this gives an upper bound on the total time:
So if \(p_i = O(T(n))\), then \(O(T(n))\) is an upper bound on the amortized complexity.
Example: resizing a dynamic array
Take insertion into the dynamic array vector again. Let \(h_0\) be the initial state, and define the potential function \(\Phi(h)\) as follows:
Here \(n\) is the number of elements in the array and \(m\) is its current capacity. Changes in this potential function reflect how the credit stored to pay for future resizes rises and falls. In the initial state, an empty array of capacity \(1\), we have \(\Phi(h_0)=-1\). In every non-empty state reachable by insertions alone, with doubling when full, \(m\leq 2n\), so \(\Phi(h)\geq 0>\Phi(h_0)\).
-
Insertion (no resize needed):
- Cost of the operation: \(O(1)\), since only one element is inserted.
- Change in potential: after the insertion the number of elements has grown by 1, so the potential increases by \(2\).
- \(\Phi(h') - \Phi(h) = 2(n + 1) - m - (2n - m) = 2\).
- Amortized cost: \(1 + 2 = 3\).
-
Insertion (triggers a resize):
- Suppose the current capacity is \(m = n\). Inserting a new element triggers a resize, and the new capacity is \(2n\).
- Cost of the operation: \(O(n)\), since all elements have to be copied into the new array and the new element inserted.
- Change in potential: resizing and inserting changes the potential by \(2-n\), so it decreases only when \(n>2\).
- \(\Phi(h') - \Phi(h) = 2(n + 1) - 2n - (2n - n) = 2 - n\).
- Amortized cost: \(n + 1 + (2 - n) = 3\).
This analysis shows that although a resize has a high actual cost, the way the potential function is designed keeps the overall amortized cost constant, \(O(1)\).
Extended example: stack operations
Stack operations are one of the classic applications of amortized analysis. Suppose we start from an empty stack, pop is only applied to a non-empty stack, and the stack S supports the following three operations:
| Operation | Description | Actual cost \(c_i\) |
|---|---|---|
S.push(x) |
Push the element \(x\) | \(1\) |
S.pop() |
Pop the top element | \(1\) |
S.multi-pop(k) |
Pop up to \(k\) elements from the top | \(O(\min(\lvert S\rvert,k))\) |
We analyze the amortized cost of these stack operations with each of the three methods: aggregate analysis, the accounting method and the potential method.
Aggregate analysis
Aggregate analysis computes the total cost of all operations and spreads it evenly over them, which gives the amortized cost.
- The \(n_{\text{push}}\)
push(x)operations cost \(O(1)\) each, so \(O(n_{\text{push}})\) in total. - The \(n_{\text{pop}}\)
pop()operations cost \(O(1)\) each, so \(O(n_{\text{pop}})\) in total. - Each of the \(n_{\text{multi-pop}}\)
multi-pop(k)operations has actual cost \(O(\min(\lvert S \rvert, k))\), but together they cannot pop more elements than earlierpush(x)operations pushed, so their total cost is still bounded by \(n_{\text{push}}\).
The total number of operations is \(n=n_{\text{push}}+n_{\text{pop}}+n_{\text{multi-pop}}\), and \(n_{\text{push}}\le n\). Each element is pushed at most once and popped at most once, so the total cost charged per element is \(O(n_{\text{push}})=O(n)\). Even if we also count the constant overhead of the check in every call, the total cost is still \(O(n)\), which is \(O(1)\) amortized.
Accounting method
The accounting method sets aside some credit at each push(x) to pay for a possible future pop() or multi-pop(k).
S.push(x): give eachpush(x)an amortized cost of \(2\). Of this, \(1\) unit pays for the operation itself, and the other \(1\) unit is stored as credit to pay for a futurepop()ormulti-pop(k).S.pop(): the actual cost is \(1\), but an earlierpush(x)has already stored \(1\) unit of credit for it, so the amortized cost is \(0\).S.multi-pop(k): each popped element has actual cost \(1\), which is paid by the credit that thepush(x)of that element stored earlier, so the amortized cost is \(0\).
So the credit stored by a push is enough to pay for the later pop of the same element, and the amortized cost of every operation is \(O(1)\).
Potential method
The potential method defines a potential function that measures the state of the stack, and uses changes in potential to balance the costs of the operations.
- Potential function: let \(\Phi(h)\) be the number of elements in the stack, that is, \(\Phi(h) = \lvert S \rvert\). Each element contributes \(1\) unit of potential.
S.push(x): eachpush(x)adds an element to the stack and raises the potential by \(1\), so its amortized cost is \(1 + 1 = 2\).S.pop(): eachpop()removes an element from the stack and lowers the potential by \(1\), so its amortized cost is \(1 - 1 = 0\).S.multi-pop(k): let \(t=\min(\lvert S\rvert,k)\). Amulti-pop(k)actually pops \(t\) elements and lowers the potential by \(t\), so the amortized cost charged per element is \(t-t=0\); counting the overhead of the call, it is \(O(1)\).
With this potential function, push(x) has amortized cost \(2\), while pop() and multi-pop(k) have amortized cost \(0\). So every stack operation has amortized cost \(O(1)\).
References and notes
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: yyyu-star, 24OI-bot, HeRaNO, jyeric, Tiphereth-A, c-forrest, not-exist (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.