Extra memory is the space an algorithm uses beyond the memory already occupied by the data structure it operates on. Space generally means all memory used, regardless of whether it lives in RAM, on disk, or in cache. section 4.12
Use extra-memory analysis to compare how an algorithm handles growing input:
- An algorithm that creates another array of size n uses O(n) extra space. section 4.12
- An in-place algorithm that swaps elements with one fixed variable uses O(1) extra space. section 4.12
- Count memory allocated during the operation even if some of it is freed later. section 5.16
Resizing a dynamic array
A dynamic-array insert normally uses O(1) extra memory. When the array is full, resizing creates a new array, copies all n elements, and temporarily uses O(n) extra space. Thus, insertion has O(n) worst-case extra space but O(1) extra space when resizing is unnecessary. section 5.16
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.
The resizing helper makes the additional allocation and element copying visible. section 5.16
