Amortized analysis bounds the total cost of a sequence of operations rather than promising that every individual operation is fast. An occasional expensive operation can be spread across many inexpensive ones, producing a worst-case guarantee for the combined sequence. section 4.11
Use the distinction between analysis types to interpret performance:
- Worst-case analysis reports how slow one unlucky operation can be. section 4.11
- Average-case analysis describes expected performance but does not guarantee a particular run. section 4.11
- Amortized analysis guarantees the growth of the total cost across many operations. section 4.11
Dynamic-array insertion
A dynamic array normally inserts in O(1), but inserting into a full array may resize it and copy every element. Starting with capacity one and doubling it moves 1 + 2 + 4 = 7 elements to reach eight elements. Across n insertions, the copying totals O(n), so the sequence has O(n) amortized time even though one insertion may be slow. section 5.16 section 5.19
def _double_size(self):
old_array = self._array
self._array = core.Array(self._capacity * 2, self._typecode) #1
self._capacity *= 2
for i in range(self._size): #2
self._array[i] = old_array[i]
#1 After saving a reference to the old array in a local variable, we can create a new array twice as large.
#2 We need to copy all the elements from the old array to the new one.
Inspect the resize operation that allocates a doubled array and copies the existing elements. section 5.16
