Question 1. (20 marks) Suppose we have an array A[1,2,...] supporting the following two operations: INSERT...

 

Transcribed Image Text:

Question 1. (20 marks) Suppose we have an array A[1,2,...] supporting the following two operations: INSERT (T) k=k+1 A[k]:=x PRINTANDREDUCE() (* k is a global variable initialized to 0 *) for i = 1 to k do print A[i] endfor k := = [k/3] (* note that this for loop uses k *) The cost of each operation is defined as follows: The cost of INSERT(x) is exactly 1. The cost of PRINTANDREDUCE() is the exact value of the global variable k just before PRINTANDREDUCE() 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)/n. What is the best (i.e., smallest) upper bound for T(n)/n in the sorted list L below? n L= 11, 1, 3, 2, 2, 2, 3, 7, 4, 2, 5, log3 n, n, logan n. Justify your answer (answers with no proofs 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. (20 marks) Suppose we have an array A[1,2,...] supporting the following two operations: INSERT (T) k=k+1 A[k]:=x PRINTANDREDUCE() (* k is a global variable initialized to 0 *) for i = 1 to k do print A[i] endfor k := = [k/3] (* note that this for loop uses k *) The cost of each operation is defined as follows: The cost of INSERT(x) is exactly 1. The cost of PRINTANDREDUCE() is the exact value of the global variable k just before PRINTANDREDUCE() 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)/n. What is the best (i.e., smallest) upper bound for T(n)/n in the sorted list L below? n L= 11, 1, 3, 2, 2, 2, 3, 7, 4, 2, 5, log3 n, n, logan n. Justify your answer (answers with no proofs 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.