Explain the amortized cost difference between appending to a linked list with a tail pointer vs appending to a dynamic array that occasionally resizes.

• A. Linked list append is O(1) amortized; dynamic array append is amortized O(1) but may incur occasional O(n) resizes.
• B. Linked list append is O(log n); dynamic array is O(1) always.
• C. Both are O(n) amortized.
• D. Dynamic array resizes cause O(n) log n amortized.

Answer: (A)

Amortized analysis here shows that appending to a linked list with a tail pointer is consistently constant work: you attach a new node after the tail and move the tail reference, with no resizing or copying involved. Over a sequence of appends, the average cost per append stays O(1) because every operation does roughly the same amount of work.

A dynamic array that doubles its capacity when full behaves similarly most of the time, but with a twist. Most appends just place the element in the next free slot for a cost of 1. Occasionally, when the array is full, you must allocate a larger array and copy all existing elements over, which costs O(n) for n elements. That expensive resize is the spike, but across many appends its cost is spread out, keeping the average (amortized) cost per append at O(1). The occasional O(n) resize is the point where the operation isn’t strictly constant, but it doesn’t ruin the overall constant amortized cost.

So the best description is: Linked list append is O(1) amortized; dynamic array append is amortized O(1) but may incur occasional O(n) resizes. The other options don’t fit because they misstate the typical costs or ignore the amortized analysis of resizes.