Differentiate between amortized and worst-case time complexity with an example.

• A. Amortized time complexity considers a single operation; worst-case averages across a sequence.
• B. Amortized averages over a sequence of operations; worst-case is the maximum for a single operation.
• C. Amortized is always better than worst-case.
• D. Worst-case is about average.

Answer: (B)

The main idea here is how cost is measured over time: amortized looks at the average cost per operation across a sequence, while worst-case looks at the maximum cost for a single operation in a given scenario. Amortized time complexity distributes occasional expensive steps over many cheap ones, giving a stable average per operation when you perform many operations in a row.

A classic example is adding elements to a dynamic array that doubles its capacity when full. Most insertions are cheap, but when the array is full a resize occurs, which requires copying all existing elements to a new, larger array. If you perform n insertions, the total work ends up proportional to n plus the copies done during resizes, which turns out to be about 2n. So the average cost per insertion—the amortized cost—is constant (O(1)). Yet the single insertion that triggers a resize can be quite expensive, costing proportional to the current number of elements (O(n)) in the worst case.

This aligns with the statement that amortized averages over a sequence of operations, while the worst-case is the maximum cost for a single operation. The other descriptions mix up these ideas: amortized is not about a single operation, and worst-case is not about the average.