Question 1. (1 marks) Suppose we have an array A[1,2,...] supporting the followi

Question

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(x) k:= k + 1 A[k] := x OUTPUTAndREDuCE for i = 1 to k do print Ali) endfor (this for loop includes k) The cost of each operation is defined as follows: . The cost of INSERT() is exactly 1. The cost of OUTPUTANDREDUCEis 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)/n What is the best (i.e., smallest) upper bound for T(n)/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

Explanation / Answer

Solution:

Well, the for loop is running k number of times and the value of k is changing k= k/3 at every iteration

so if the value of K = 2187, the loop will go like this

Iteration 1: for 1 to 2187

Iteration 2: for 2 to 729

Iteration 3: for 3 to 243

Iteration 4: for 4 to 81

Iteration 5: for 5 to 27

Iteration 6: for 6 to 9

So the worst case running will be T(n) = log3 n

So amortized cost per operation = log3 3/3= 1/3

for k = 9

log3 9/9= 2/9

So, now we can conclude that the smallest upper bound is= 1/2.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.