Data structures that have to grow over time are sometimes implemented using a do
ID: 3682732 • Letter: D
Question
Data structures that have to grow over time are sometimes implemented using a doubling scheme. It works something like this. Start with a data structure that can hold one element. Suppose later the data structure has the capacity to hold k elements, and is at capacity, that is, it is holding k elements. Now, suppose you want to add a new element x to the data structure. In that case, here’s what we do. We allocate space for a new data structure that can hold 2k elements, we copy the k elements from the old data structure into the new one, we add the new element x to the new data structure, because there is room. We delete the old data structure, and we replace it with the new one. Suppose that doing this costs time O(k). That is, the cost of doubling a data structure of size k is proportional to the number of elements that have to be copied. You might notice that as elements are added to the data structure the size of the data structure doubles from time to time, going from size 1 to size 2 to size 4, and so on.
Let’s call the operation of adding an element x to the data structure, Append(x). Sometimes doing an Append(x) costs O(1), when the data structure has room for x. Sometimes, doing an Append(x) could be quite slow, because it requires copying the whole existing data structure to a new place.
If you start with a data structure that holds one element, and then execute a sequence of n Append’s, what is the total cost of all the Appends?
Explanation / Answer
The data structure which we are thinking here is array. Array are similar in behavour and adding a new element is O(1) till the time we have space in the array. If the array is filled up then we need to do copy operation and then continue adding the remaining elements to the new array.
For n appends it may be done in O(1) if the size of the array is k>n but since here we have size of array as 1.
it will become a series like O(1+2+4+8+........2*n)
O(2n-1) using geometric progression formula with a =1 r =2.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.