Table of Contents
Dynamic arrays are data structures that automatically resize when they reach capacity. Understanding their amortized cost helps evaluate their efficiency over multiple operations.
What is Amortized Cost?
The amortized cost is the average cost per operation over a sequence of operations. It smooths out the high costs of occasional resizing by distributing them across many inexpensive operations.
Dynamic Array Operations
Common operations on dynamic arrays include insertion, deletion, and resizing. Insertion at the end is typically the most frequent operation, which may trigger resizing when capacity is exceeded.
Calculating the Amortized Cost
When inserting elements, the array doubles in size when full. The cost of resizing involves copying all existing elements to the new array. Although resizing is costly, it occurs infrequently.
For example, if an array starts with capacity 1, the sequence of resizing costs over multiple insertions can be summarized as:
- Insert 1 element: cost 1
- Insert 2nd element: resize (cost 1), total cost 2
- Insert 3rd element: resize (cost 2), total cost 3
- Insert 4th element: resize (cost 4), total cost 4
The total cost over n insertions is proportional to 2n, making the amortized cost per insertion approximately O(1).