Amortized analysis
Amortized analysis bounds the average cost of an operation over a worst-case sequence of operations. It is different from average-case analysis: no probability or random input is involved. It guarantees that any sequence of n operations costs at most n times the amortized bound in total, even though an individual operation can be expensive.
Python
class DynamicArray:
def __init__(self):
self.capacity = 1
self.size = 0
self.copies = 0
def append(self):
if self.size == self.capacity:
self.capacity *= 2
self.copies += self.size
self.size += 1
array = DynamicArray()
for _ in range(16):
array.append()
print(array.size, array.capacity, array.copies)
print(array.copies / array.size)
assert array.copies < 2 * array.size