Amortized Complexity

Prerequisite knowledge: Time Complexity

This page introduces the basics of amortized complexity.

Introduction

Amortized analysis (Amortized Analysis) is a technique for analyzing the performance of algorithms and dynamic data structures. It focuses not only on the cost of a single operation, but also evaluates the average cost of a sequence of operations to provide a more accurate assessment of overall performance. Amortized analysis does not involve probability; it can only guarantee the average time spent by each operation in the worst case, and cannot determine the average performance of a system. In the worst case, amortized analysis distributes the cost of high-cost operations among low-cost operations, ensuring that the average cost of all operations remains within a reasonable range.

Amortized analysis usually uses three main analysis methods: aggregate analysis, accounting analysis, and potential analysis. Each method emphasizes a different aspect and applies to different scenarios, but their common goal is to optimize the overall performance of a data structure in the worst case by balancing operation costs.

Content

Consider a dynamic array, such as vector in C++, whose initial capacity is $m = 1$. Each time a new element is inserted, if the array is full, its size must be doubled, then the elements in the original array are copied to the new array, and finally the new element is inserted.

Next, using insertion into a dynamic array as an example, we analyze its amortized cost with the three methods of aggregate analysis, accounting analysis, and potential analysis.

Aggregate Analysis

Aggregate analysis (Aggregate Analysis) calculates the total cost of a sequence of operations and averages it over each operation to obtain the amortized time complexity of each operation.

For a dynamic array, we can first identify two key costs of an insertion operation:

• If the array is not full, the cost of the insertion operation is $O(1)$.
• If the array is full, the insertion operation requires expansion. The cost of copying elements after expansion is $O(m)$, where $m$ is the current size of the array.

Therefore, to calculate the total cost of n insertion operations, we can divide it into two parts:

1. Cost of insertion operations: The direct cost of inserting a new element each time is constant time $O(1)$, so the total cost for $n$ operations is $O(n)$.
2. Cost of array expansion: Each expansion involves copying the elements of the original array to the new array. These operations occur when the array size is $1, 2, 4, \ldots , 2^k$, where $2^k$ is the largest power less than or equal to $n$. The costs of the expansion operations are $1, 2, 4, \ldots , 2^{k-1}$, whose sum is $1 + 2 + 4 + \ldots + 2^{k-1} = 2^k - 1$. This is the sum of a geometric sequence, and its result is $O(n)$.

Therefore, the total insertion cost of the array is $O(n)$, and the amortized cost per operation is $O(1)$. Even in the worst case, the average cost of each insertion operation is still constant time.

Accounting Analysis

The accounting method (Accounting Method) preallocates a fixed amortized cost for each operation to ensure that the total cost of all operations does not exceed the sum of these preallocated costs. The accounting method is similar to a mechanism of prepaying costs, in which low-cost operations store part of their cost to pay for future high-cost operations.

For a dynamic array, a fixed amortized cost can be assigned to each insertion operation to ensure that enough cost has been reserved when expansion is needed.

1. Cost allocation:

   • Suppose the actual cost of each insertion operation is $1$, and its amortized cost is set to $3$.
   • Of this, $1$ is used for the current insertion operation, and $2$ is used for a possible future expansion operation.

2. Cost usage:

   • When the array is full, an expansion operation is required, with an actual cost of $O(m)$, where $m$ is the current size of the array.
   • Suppose the number of elements in the array before expansion is $n$. Since the $n/2$ elements in the latter half of the original array have collectively stored $n$ units of amortized cost during insertion, this is exactly enough to pay the cost of the expansion operation.

Here is a specific example:

Initial state:
arr    = [1, 2, 3, 4]  // Initial array
amount = [2, 2, 2, 2]  // Prepaid cost for each element

// First expansion: the array is full and needs to be expanded
arr    = [1, 2, 3, 4, null, null, null, null]  // Array after expansion
amount = [2, 2, 0, 0, 0, 0, 0, 0]  // The costs for 3 and 4 are used to pay for the expansion

// Continue inserting new elements until the array is full again
arr    = [1, 2, 3, 4, 5, 6, 7, 8]  // Continue filling the array
amount = [2, 2, 0, 0, 2, 2, 2, 2]  // Newly inserted elements also store prepaid costs

// Second expansion: the array is full again and needs more space
arr    = [1, 2, 3, 4, 5, 6, 7, 8, null, null, null, null, null, null, null, null]  // Array after expansion
amount = [2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]  // The costs for 5, 6, 7, and 8 are used to pay for the expansion

The process above shows that the amortized cost stored by each insertion operation is sufficient to pay for future expansion operations, ensuring that the amortized cost of each operation remains $O(1)$.

Potential Analysis

The potential method (Potential Method) defines a potential function, usually denoted by $\Phi$, to measure the potential energy of a data structure, namely the resources reserved in the system state that can be used to pay for future high-cost operations. Changes in potential balance the total cost of an operation sequence, ensuring that the amortized cost of the entire algorithm remains within a reasonable range.

Principle

First, define the state $S$ as the state of the data structure at a certain point in time. This state may include the number of elements, capacity, pointers, and other information. Define the initial state as $S_0$, the state before any operation has been performed.

Next, define a potential function $\Phi(S)$ to measure the potential of data structure state $S$. It satisfies the following two properties:

1. Initial potential: In the initial data structure state $S_0$, the potential is $\Phi(S_0) = 0$.
2. Non-negativity: For any state $S$, the potential satisfies $\Phi(S) \geq 0$.

For each operation, its amortized cost $\hat{c}$ is defined as:

$$\hat{c} = c + \Phi(S') - \Phi(S)$$

Here, $c$ is the actual cost of the operation, and $S$ and $S'$ represent the states of the data structure before and after the operation, respectively. This formula shows that the amortized cost equals the actual cost plus the change in potential. If an operation increases the potential (that is, $\Phi(S') > \Phi(S)$), the amortized cost increases; if an operation consumes potential (that is, $\Phi(S') < \Phi(S)$), the amortized cost decreases.

We can use the potential function to analyze the total cost of a sequence of operations. Let $S_1, S_2, \dots, S_m$ be the sequence of states produced starting from initial state $S_0$ after $m$ operations, and let $c_i$ be the actual cost of the $i$-th operation. Then the amortized cost of the $i$-th operation, $p_i$, is:

$$p_i = c_i + \Phi(S_i) - \Phi(S_{i-1})$$

Therefore, the total time cost of $m$ operations is:

$$\sum_{i=1}^m c_i = \sum_{i=1}^m p_i + \Phi(S_0) - \Phi(S_m)$$

Since $\Phi(S) \geq \Phi(S_0)$, the upper bound on the total time cost is:

$$\sum_{i=1}^m p_i \geq \sum_{i=1}^m c_i$$

Therefore, if $p_i = O(T(n))$, then $O(T(n))$ is an upper bound on the amortized complexity.

Example: Analysis of Dynamic Array Expansion

Taking insertion into a dynamic array vector as an example, define the following potential function $\Phi(h)$:

$$\Phi(h) = 2n - m$$

Here, $n$ is the number of elements in the array, and $m$ is the current capacity of the array. This potential function reflects the amount of available space remaining in the array, namely the difference between the current capacity and the amount of space actually used.

1. Insertion operation (no expansion required):

   • Operation cost: $O(1)$, because only one element needs to be inserted.
   • Change in potential: After insertion, the number of elements increases by 1, and the potential increases by $2$.
     • $\Phi(h') - \Phi(h) = 2(n + 1) - m - (2n - m) = 2$
   • Amortized cost: $1 + 2 = 3$

2. Insertion operation (triggering expansion):

   • Suppose the current capacity is $m = n$. Inserting a new element triggers expansion, and the new capacity becomes $2n$.
   • Operation cost: $O(n)$, because all elements need to be copied to the new array and the new element needs to be inserted.
   • Change in potential: After expansion, the capacity increases and the potential decreases by an amount of $2 - n$.
     • $\Phi(h') - \Phi(h) = 2(n + 1) - 2n - (2n - n) = 2 - n$
   • Amortized cost: $n + 1 + (2 - n) = 3$

The analysis above shows that although the actual cost of an expansion operation is high, the overall amortized cost remains at the constant level $O(1)$ due to the design of the potential function.

Extended Example: Stack Operations

Stack operations are one of the classic application scenarios of amortized analysis. Suppose stack S supports the following three operations:

We analyze the amortized cost of these stack operations using aggregate analysis, accounting analysis, and potential analysis.

Aggregate Analysis Method

Aggregate analysis calculates the total cost of all operations and averages it over each operation to obtain the amortized cost.

1. For $n_{push}$ push(x) operations, each operation costs $O(1)$, so the total cost is $O(n_{push})$.
2. For $n_{pop}$ pop() operations, each operation costs $O(1)$, so the total cost is $O(n_{pop})$.
3. For $n_{multi-pop}$ multi-pop(k) operations, although the actual cost of each operation is $O(\min(\lvert S \rvert, k))$, the number of elements popped by these operations cannot exceed the number of elements previously added by push(x), so the total cost is still bounded by $n_{push}$.

Since the total number of operations $n = n_{push} + n_{pop} + n_{multi-pop} \leq 2 \times n_{push}$, the total cost is $O(n_{push}) = O(n)$, and the amortized cost per operation is $O(n)/n = O(1)$.

Accounting Analysis Method

Accounting analysis reserves part of the cost for each push(x) operation to pay for possible future pop() or multi-pop(k) operations.

1. S.push(x): Suppose the amortized cost of each push(x) operation is $2$. $1$ unit is used for the current operation, and another $1$ unit is stored as credit to pay for a future pop() or multi-pop(k) operation.
2. S.pop(): The actual cost is $1$, but because previous push(x) operations have prepaid $1$ unit of credit for it, the amortized cost is $0$.
3. S.multi-pop(k): The actual cost of popping each element is $1$, which can be paid by the credit prepaid by the previous push(x) operation for that element, so the amortized cost is $0$.

The analysis above shows that the credit prepaid by a push operation is sufficient to pay for the future pop operation of that element, so the amortized cost of each operation is $O(1)$.

Potential Analysis Method

Potential analysis defines a potential function to measure the state of the stack and uses changes in potential to balance operation costs.

1. Potential function: Let $\Phi(h)$ be the number of elements in the stack, namely $\Phi(h) = \lvert S \rvert$. Each element contributes $1$ unit of potential.
2. S.push(x): Each push(x) operation increases the number of elements in the stack, increasing the potential by $1$. Therefore, the amortized cost is $1 + 1 = 2$.
3. S.pop(): Each pop() operation decreases the number of elements in the stack, decreasing the potential by $1$. Therefore, the amortized cost is $1 - 1 = 0$.
4. S.multi-pop(k): A multi-pop(k) operation pops $k$ elements, decreasing the potential by $k$. Therefore, the amortized cost is $k - k = 0$.

With the potential function designed as above, the amortized cost of a push(x) operation is $2$, while the amortized costs of pop() and multi-pop(k) operations are $0$. Therefore, the amortized cost of all stack operations is $O(1)$.

References

• Amortized Analysis - Wikipedia
• Cornell CS 3110 - Lecture 20: Amortized Analysis