Consider the extensible array data structure that we learned in class. Suppose t

Question

Consider the extensible array data structure that we learned in class. Suppose there is no extra cost for allocating memory. Suppose that we want to add another operation to this data structure: Remove, which deletes the last element added. In order to make sure that the array doesn’t take up too much space, we say that if the array is at least half empty, we will reallocate memory that is only half the size of the current array, and copy all the elements over. This is basically the opposite of the insertion operation from before.

Part a: Does amortized analysis make sense here? In other words, does it allow us to get a tighter bound than the standard analysis?

Part b: Instead of reallocating memory if the array becomes half empty, we reallocate/copy if the array becomes at least 3/4 empty (only 1/4 of the array cells are being used). Analyze the running time of a sequence of n operations using amortized analysis. Hint: this is a straightforward modication of the original extensible array analysis. If we shrink an array, how many elements get added before we next double it? If we are deleting elements, how many do we delete before shrinking it?

Explanation / Answer

a.) Yes .Amortized analysis is used for finding the worst case analysis from a given set of operations.Hence it can be used to find a tight upper bound when the array size is either resized or shrinked .

b.) suppose the size of the array is n.and the first shrinking occurs when 3/4th of the array is empty ie, the array shrinking occurs while removing n/4 +1 th element. The next shrinking occurs while removing 1/4(n/4+1)+1. and so on untill n =1. So the complexity is of O(n). We shrink an array when atleast 3/4th array is empty and changed to array of of size n/4.so we may need to fill up to n/4th element to make it full and double its size.

. If we are deleting we need to delete 3/4 th of the array before we shrink the array to 1/4th. Ie the array is shrinked while deleting n/4+1 th element.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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