Question

In class we analyzed Dynamic Table Expansion under the assumption that if we want to insert a new element in a table T that is full, we insert copy all the elements of T into a new table T ' of size |T '| = 2|T|, and then enter the new element in T '. In this question, we consider cases where the size of T ' is not double the size of T. Assume (as in class) that entering an element in an empty slot of a table costs 1, and copying an element from a table into a new table also costs 1. Suppose that |T '| = |T| + 1000, i.e, each new table has 1000 more slots than the previous one. Starting with an empty table T with 1000 slots, we insert a sequence of n elements. What is the amortized cost per insertion?

Answer 1

The amortized cost per insertion, when a table expands by 1000 slots each time it is full, is slightly more than 1 but less than 2. This cost includes both the insertion and the copying needed during table expansions, factoring the growing cost of copying as the number of elements increases.

Step-by-step explanation:

In a scenario where a dynamic table increases in size by 1000 slots each time it is expanded, and the cost of each operation (inserting or copying an element) is 1, the amortized cost per insertion needs to be calculated. To determine the amortized cost, we can use the aggregate method. This looks at the total cost of a sequence of operations and divides by the number of operations performed.

Imagine an initial empty table T with 1000 slots and a sequence of n insertions. Each time the table is full, it gets expanded by 1000 new slots and all the elements are copied to the new table before the next element is inserted. The cost of a copy operation grows linearly with the number of elements, and every expansion allows for an additional 1000 insertions without further copying.

The total cost for n insertions can be calculated by summing the cost of each expansion. The table starts with 1000 slots and grows by 1000 each time, so expansions happen every 1000 insertions. Every time an expansion occurs, all elements are copied, so after k expansions we have k*1000 copy operations. Adding the cost of the actual insertions (which is always 1 per insertion), the total cost for n insertions is n + k*1000 where k = ⌊n/1000⌋.

The amortized cost per insertion is then the total cost divided by n, which simplifies to slightly more than 1 but less than 2, as the number of expansions is significantly smaller than the number of insertions.