Assume that we need to store a stream of keys arriving to our program.

4. Assume t hat we need to store a st ream of keys arriving to our program. We would like to store them in an array A[1 n]. Thefirst arriving key must bestored at location A[1], the second at A12], the third at A[3] and so on. However, we have no idea about the number of keys that we will receive, and our programming language (such as C) requires that we allocat e any contiguous array we are using. Hence, the following solution is proposed (see Figure 1): Start by allocating an array A[1 4. we set m = 4, and set j = 1, The following code is executed upon arrival of a new key Algorithm Insert(x, A) Input: x is the ith key that has arrived. A is an array of size m ("So far we have written keys into A[1 1] while Ali, . . . m] is still free, 2.ifi=m 3. then Allocate a new array B[1 2m]. (-n C', you might use the com- mand 'malloc' or 'new' for j 1 m, oopy BU] AU]. Clear all content s of A, and rename array B as array A (constant time operation) m 2m 5. 6. 7. 8 . INSERT 2. INSERI 3. INSERT 4. INSERI 5. INSEKT 1. INSERT 2. INSERT 3. INSERT 4. INSERT 5, INSERT . INSERT 2. INSERT 3, INSERT 4. INSERT 5. INSERT Figure 1: Example of the execution of Insert (x, A). Credit: Charles Leiserson This prooedure 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 AI, the length of A