Amortized analysis is a technique for analyzing the average time complexity of operations in a sequence, where some operations may be expensive but are balanced by many cheaper operations. Let’s explore each method in detail with C implementations.
1. Aggregate Analysis
Concept: In aggregate analysis, we determine an upper bound T(n) on the total cost of a sequence of n operations, then calculate the average cost per operation as T(n)/n.
Example: Dynamic array (similar to std::vector in C++) where we double the size when full.
#include Analysis:
- The cost of n push operations is O(n) because the total cost T(n) of n operations is at most n (for insertions) plus the cost of doublings (1 + 2 + 4 + … + 2^⌊log₂n⌋) = O(n).
- Thus, the amortized cost per operation is O(n)/n = O(1).
2. The Accounting Method
Concept: We assign different charges to operations (amortized costs). Some operations are charged more than their actual cost, with the excess stored as credit to pay for future expensive operations.
Example: Dynamic array using accounting method.
<em>// Same DynamicArray structure as before
void pushBackAccounting(DynamicArray *da, int value, int *credit) {
int actualCost = 1; <em>// Basic insertion cost
int amortizedCost = 3; <em>// We choose this based on analysis
if (da->size == da->capacity) {
<em>// Resizing costs 'size' (copying all elements)
actualCost += da->size;
}
<em>// Use credit to pay for actual cost
*credit += amortizedCost - actualCost;
<em>// Perform the operation
if (da->size == da->capacity) {
da->capacity *= 2;
da->array = (int *)realloc(da->array, da->capacity * sizeof(int));
}
da->array[da->size++] = value;
printf("Added %d, size=%zu, capacity=%zu, credit=%d\n",
value, da.size, da.capacity, *credit);
}
int main() {
DynamicArray da;
initArray(&da, 2);
int credit = 0;
for (int i = 0; i < 10; i++) {
pushBackAccounting(&da, i, &credit);
}
freeArray(&da);
return 0;
}Analysis:
- We assign an amortized cost of 3 per insertion.
- For non-expanding insertions: actual cost=1, credit=2
- For expanding insertions: actual cost=1 + n (copying), but we’ve saved 2*(n/2)=n credit from previous insertions
- Credit never goes negative, proving O(1) amortized cost.
3. The Potential Method
Concept: We define a potential function Φ on the data structure’s state. The amortized cost is actual cost plus change in potential.
Example: Dynamic array with potential function Φ = 2*size – capacity
<em>// Same DynamicArray structure
void pushBackPotential(DynamicArray *da, int value, int *totalAmortized) {
int actualCost = 1;
int oldPotential = 2 * da->size - da->capacity;
if (da->size == da->capacity) {
actualCost += da->size; <em>// Copy cost
}
<em>// Perform the operation
if (da->size == da->capacity) {
da->capacity *= 2;
da->array = (int *)realloc(da->array, da->capacity * sizeof(int));
}
da->array[da->size++] = value;
int newPotential = 2 * da->size - da->capacity;
int amortizedCost = actualCost + (newPotential - oldPotential);
*totalAmortized += amortizedCost;
printf("Added %d, size=%zu, capacity=%zu, amortized=%d, total=%d\n",
value, da.size, da.capacity, amortizedCost, *totalAmortized);
}
int main() {
DynamicArray da;
initArray(&da, 2);
int totalAmortized = 0;
for (int i = 0; i < 10; i++) {
pushBackPotential(&da, i, &totalAmortized);
}
freeArray(&da);
return 0;
}Analysis:
- Φ = 2*size – capacity
- For non-expanding insertions: ΔΦ = 2, amortized cost = 1 + 2 = 3
- For expanding insertions (size = capacity = n):
- Actual cost = 1 + n
- ΔΦ = 2(n+1) – 2n – (2n – n) = 2 – n
- Amortized cost = (1 + n) + (2 – n) = 3
- Thus, amortized cost is always 3 (O(1))
4. Dynamic Tables
Concept: Dynamic tables (like our dynamic array example) grow and shrink dynamically to maintain load factor. The key is to not just grow but also shrink the table when it becomes too empty, while still maintaining amortized O(1) operations.
Implementation with expansion and contraction:
#include Analysis:
- Expansion: When table is full (size = capacity), double the size
- Contraction: When table is quarter full (size = capacity/4), halve the size
- This ensures the load factor is always between 1/4 and 1
- Amortized cost is O(1) per operation using any of the three methods
Comparison of Methods
- Aggregate: Simple but less precise for complex data structures
- Accounting: More flexible, allows different operations to have different amortized costs
- Potential: Most powerful, can handle more complex scenarios, mathematically rigorous
All three methods should give the same amortized cost for the same problem, but some may be easier to apply than others depending on the situation.
Dynamic tables are a fundamental example where amortized analysis shows that even with occasional expensive operations, the average cost per operation can be constant.
