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)

Appends to a dynamic array that doubles in size illustrate how amortized time works: most appends are constant time, while occasionally a resize costs more. When the array is full, it allocates twice as much space and copies the existing elements, a cost proportional to the current size. But this big cost happens only after a number of previous appends equal to the current size, so across a long sequence of n appends, the total work is proportional to n plus the total copies done during resizes. Since each resize happens after roughly as many appends as the new capacity, the extra copying is spread out over those appends, keeping the average cost per append constant. Therefore, the amortized time for each append is O(1), with occasional O(n) time during a resize. The alternatives don’t fit: an O(n) per append would imply every append triggers a costly operation, O(log n) amortized would rise with n in a logarithmic way, and O(n^2) worst-case per append would imply extremely expensive operations on every attempt, which isn’t how doubling-resize dynamic arrays behave.