There is this proof where we have a table that can contains n elements. Each time we completely fill this table we want to transfer the elements to another table where the new table has double the size of the older one.
The goal of the proof is to prove that the cost for inserting an element in the table is 3n or can be viewed as 3 dollars. (The proof is about amortized analysis and uses the accounting method.)
The rationale behind the 3 dollar price is the following:
- 1 dollar is required for inserting the element into the table.
- 1 dollar is saved for later when we will need to transfer to the new table.
- 1 dollar is given to another element in the table to pay for its transfer when required.
If we do this each time an element is inserted into the table when the time comes to transfer, every element will have 1 dollar in credit to pay for the insertion in the new table.
Now my question isn't about this case. What I'm interested in knowing is what will be the cost if we changed the expansion from doubling the size to tripling instead. So, each time we have filled the table the new one will have 3 times the size of the one before.
After thinking about it for some time I concluded that it would be (1 + 1/2)n with the following rationale:
- 1 dollar is spent for inserting the element.
- 1 dollar is saved for that element to moved itself to the new table when required to.
- 1/2 dollar is given to another element in the table to help pay its transfer to the new table.
Therefore we have (1+ 1/2) dollars.
I wonder if what I've found is correct or not.