2. [14] Suppose that we have an array Al1,2...] (index starting at 1) that is sufficiently large, and supports the following two operations INSERT and PRINT-AND-CUT (where k is a global variable initially set to 0): 1 def INSERT (x) 2 k -k + 1 A[k] = x 5 def PRINT-AND-CUT O) 6 for i from 1 to k print A[k] # integer division We define the cost of the above two operations as follows: The cost of INSERT is exactly 1 The cost of PRINT-AND-CUT is exactly the value of k before the operation is executed. Now consider any sequence of n of the above two operations. Starting with k 0, perform an amortized analysis using the following two techniques. (a) Use the aggregate method: First, describe the worst-case sequence that has the largest possible total cost, then find the upper-bound on the amortized cost per operation by dividing the total cost of the sequence by the number of operations in the sequence. (b) Use the accounting method: Charge each inserted element the smallest amount of "dollars" such that the total amount charged always covers the total cost of the operations. The charged amount for each insert will be an upper-bound on the amortized cost per operation. Note: Your answer should be in exact forms and your upper-bound should be as tight as possible. For example, 7 would be a tighter upper-bound than 8, log2 n is tighter than n, and 4n is tighter than 5n. Your upper-bound should also be a simple term like 7, 8 or 3log n, rather than something like (5n2 -n logn)/. Make sure your answer is clearly justified. 2. [14] Suppose that we have an array Al1,2...] (index starting at 1) that is sufficiently large, and supports the following two operations INSERT and PRINT-AND-CUT (where k is a global variable initially set to 0): 1 def INSERT (x) 2 k -k + 1 A[k] = x 5 def PRINT-AND-CUT O) 6 for i from 1 to k print A[k] # integer division We define the cost of the above two operations as follows: The cost of INSERT is exactly 1 The cost of PRINT-AND-CUT is exactly the value of k before the operation is executed. Now consider any sequence of n of the above two operations. Starting with k 0, perform an amortized analysis using the following two techniques. (a) Use the aggregate method: First, describe the worst-case sequence that has the largest possible total cost, then find the upper-bound on the amortized cost per operation by dividing the total cost of the sequence by the number of operations in the sequence. (b) Use the accounting method: Charge each inserted element the smallest amount of "dollars" such that the total amount charged always covers the total cost of the operations. The charged amount for each insert will be an upper-bound on the amortized cost per operation. Note: Your answer should be in exact forms and your upper-bound should be as tight as possible. For example, 7 would be a tighter upper-bound than 8, log2 n is tighter than n, and 4n is tighter than 5n. Your upper-bound should also be a simple term like 7, 8 or 3log n, rather than something like (5n2 -n logn)/. Make sure your answer is clearly justified