Algorithm Insert(x, A)

Input: x is the i th key that has arrived. A is an array of size m. ( So far we have written keys into A[1 . . . i 1] while A[i, . . . m] is still free. )

1. A[i] x ; i + +

2.

if i = m

3. then

4. Allocate a new array B[1 . . . 2m]. ( In C, you might use the command malloc or new )

5. for j = 1 . . . m, copy B[j] A[j].

6. Clear all contents of A, and rename array B as array A (constant time operation)

7. m 2m.

This procedure is sometimes referred to as the Dynamic Table Technique. Questions:

(a) What is the worst case running time for a single Insert operation, as a function of |A|, the length of A? 3

(b) Starting from an initially empty array A, what is the worst case running time for a sequence of n Insert operations?

(c) Let > 0 be a positive constant. Assume that we modify the Insert algorithm such that once the current array A is full, we allocate a new table B of size dm(1 + )e, copy all keys from A into B, and rename B as A. Here m is the number of entries (size) of B. Note that the algorithm Insert(x, A) discussed above is just a special case of this algorithm, when = 1. What is the running time (as a function of n and ) of this algorithm when inserting n keys into an (initially empty) array A of size 1?

(d) What would be the running time of inserting a sequence of n keys into the array, if we use the following rule: If A is full, we allocate a new array B of size m+, copy all keys from A into B and rename B as A. Here, m is the number of entries (size) of A.