Algorithm Insert(r, 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.) A[i] leftarrow x: I ++ if i = m then Allocate a new array B [1 .. 2m]. (In C, you might use the command malloc or new) for j = 1 .. m, copy B[j] leftarrow A [j]. Clear all contents of A, and rename array B as array A (constant time operation) m leftarrow 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? (b) Starting from an initially empty array A, what is the worst case running time for a sequence of n Insert operations? (c) Let alpha > 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 [m(1+ alpha)], 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 alpha = 1. What is the running time (as a function of n and alpha) 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 + alpha, copy all keys from A into B and rename Bas A. Here, m is the number of entries (size of A