Question 1. (1 marks) Suppose we have an array A[1,2,.. supporting the following two operations (where k is a global variable initially set to 0) INSERT(z) k:= k + 1 A[k] :=x OUTPUTANDREDUCE for i = 1 to k do print A[i] endfor (this for loop includes k) The cost of each operation is defined as follows: The cost of INSERT(r) is eractly 1 . The cost of OUTPUTANDREDUCE) is the exact value of the global variable k just before OUTPUTANDREDUCE) is executed (because this operation prints k elements) Let T(n) be the worst-case total cost of executing any sequence of n of the above operations, starting with k = 0, The amortized cost per operation is T(n). What is the best (i.e., smallest) upper bound for T(n) in the sorted list L below? Justify your answer (unjustified answers do not get credit) HINT: Use the accounting method and charge each INSERT the smallest amount listed in L such that the total amount charged always covers the total cost of operations Question 1. (1 marks) Suppose we have an array A[1,2,.. supporting the following two operations (where k is a global variable initially set to 0) INSERT(z) k:= k + 1 A[k] :=x OUTPUTANDREDUCE for i = 1 to k do print A[i] endfor (this for loop includes k) The cost of each operation is defined as follows: The cost of INSERT(r) is eractly 1 . The cost of OUTPUTANDREDUCE) is the exact value of the global variable k just before OUTPUTANDREDUCE) is executed (because this operation prints k elements) Let T(n) be the worst-case total cost of executing any sequence of n of the above operations, starting with k = 0, The amortized cost per operation is T(n). What is the best (i.e., smallest) upper bound for T(n) in the sorted list L below? Justify your answer (unjustified answers do not get credit) HINT: Use the accounting method and charge each INSERT the smallest amount listed in L such that the total amount charged always covers the total cost of operations