Amortized Analysis

overview

Summary

Amortized analysis studies the cost of a sequence of operations. It reports an average per operation over the sequence. Use amortized_analysis to show that bursts of expensive steps still yield low amortized_cost. Common techniques: aggregate_method, accounting_method, and potential_method. Classic examples include dynamic_array resizing and a binary_counter increment. It differs from probabilistic average_case analysis. It can prove constant time per operation despite occasional worst_case spikes.