Suppose that you have a dynamic array. If the array has room available when you

Question

Suppose that you have a dynamic array. If the array has room available when you want to append an element, the cost is just O(1). But if the array is full when you want to append an element, the cost will be O(1) plus a cost to expand the array. Expanding the array means that you will double its current size. It also means that you will have to copy each element from the “old” array into the “new” (expanded) array. A copy operation costs O(1) per element copied. Using the aggregate method, show that the amortized cost of n append operations is O(1).

Explanation / Answer

The aggregate method says that instead of being concerned about the complexity of the individual operations, we worry about the compexity of rather collective operations.

For above case of dynamic arrays, If we have already allocated space for the new entry, adding it will be O(1). But if we haven't allocated it, we will do so by allocating twice the current amount. This insertion in particular would not take O(1), but rather smething else.

So, we can safely deduce that after a sequence of few operations(which do not need to expand the array) and some other operations (which require expanding the array) would take, on average, a constant amount of time, wherein less expensive operations will amortize the more expensive operations and thereby rendering the entire operation O(1).

For Example, consider a dynamic array of size 6. It would take constant time to push 6 elements. But pushing the 7th element in this array would take longer a new array of size 12 would have to be created and all the elements from the old array would have to be copied into the new array and then add the new element.

Now, the next five push operations would again take constant time, and then subsequent addition would require another slow operation of doubling the array.

Mathematially, if we consider an arbitrary number of pushes (n + 1) to an array of size n, we notice that push operations take constant time, except for the nth element which takes O(n) time to perform the expensive operation of doubling the size of the array. Since the number of operations were (n+1), we can take the average of this and we find that the push operation nin a dynamic array takes

O(n) / (n + 1) = O(1)

constant time.

Hope this helps...

BEST WISHES!

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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