In a dynamic array that resizes by doubling when full, what is the amortized time complexity of append operations?

In a dynamic array that resizes by doubling when full, what is the amortized time complexity of append operations?

• A. O(n) per append.
• B. O(1) amortized per append, with occasional O(n) resizes.
• C. O(log n) amortized.
• D. O(n^2) worst-case for each append.

Answer: (B)

The key idea here is amortized analysis for a dynamic array that doubles its capacity when full. Most appends are just inserting an element, which is a constant-time operation. Sometimes, when the array is full, you allocate a new array with twice the capacity and copy all existing elements over—that resize cost is proportional to the current number of elements. Because the capacity doubles each time, these expensive resizes happen less and less often as the structure grows. If you look at the total work to perform a sequence of n appends, the cost of all the resizes sum up to a linear amount in n, and the inexpensive appends also contribute linearly. Spread over all n appends, that averages out to a constant amount of work per append. So the typical append is O(1) on average, with occasional O(n) resizes. The other descriptions don’t match this behavior: you don’t get a steady O(n) per append, and the amortized growth isn’t O(log n) or O(n^2) per operation.

The key idea here is amortized analysis for a dynamic array that doubles its capacity when full. Most appends are just inserting an element, which is a constant-time operation. Sometimes, when the array is full, you allocate a new array with twice the capacity and copy all existing elements over—that resize cost is proportional to the current number of elements.

Because the capacity doubles each time, these expensive resizes happen less and less often as the structure grows. If you look at the total work to perform a sequence of n appends, the cost of all the resizes sum up to a linear amount in n, and the inexpensive appends also contribute linearly. Spread over all n appends, that averages out to a constant amount of work per append.

So the typical append is O(1) on average, with occasional O(n) resizes. The other descriptions don’t match this behavior: you don’t get a steady O(n) per append, and the amortized growth isn’t O(log n) or O(n^2) per operation.