Skip to main content

Amortized Analysis

Learn Amortized Analysis (Foundations, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

What Is Amortized Analysis? Some operations are usually cheap but occasionally expensive. Amortized analysis averages the cost over a whole sequence of operations, so one costly step is spread across the cheap ones. A dynamic array (like ArrayList ) doubles its capacity when full: one append may copy everything, yet the average cost per append is O(1) .

More lessons in Foundations