The banking method is sometimes used to
calculate the amortized cost of a process. In our system, every time a
value is written to memory, it will cost 1 dollar. We are going to use
this system to study the behavior of a dynamic array. The array starts
empty with some initial capacity. If an item is added to the array, a
memory write occurs, and the cost is 1 dollar. If the item added
doesn't fit in the array, a new array is allocated which is twice the
size of the previous array. All of the elements from the old array
must be copied over, costing 1 dollar for each element copied. Then the
new item must be added, costing another dollar.
For example, if 3 adds occur to an array with initial
capacity 1:
Action Capacity Size Cost Incurred
-------------------------------------------------
Start capacity = 1 size = 0 (empty)
Add capacity = 1 size = 1 (cost = 1)
Add Doesn't fit
-allocate capacity = 2 size = 0 (empty)
-copy capacity = 2 size = 1 (cost = 1)
-add capacity = 2 size = 2 (cost = 1)
Add Doesn't fit
-allocate capacity = 4 size = 0 (empty)
-copy capacity = 4 size = 2 (cost = 2)
-add capacity = 4 size = 3 (cost = 1)
So the total cost is 1+1+1+2+1 = 6.
Given the initial capacity of the empty array, and the number of adds that occur, return
the cost.
|