Module: Amortized analysis

Aggregate method, accounting method, potential method, dynamic tables, multipop example.

Learning Outcomes

Understand amortized analysis

Understand when and how to apply amortized analysis.

Readings

Introduction to amortized analysis

Aggregate, accounting, and potential methods

Screencast Suthers 23 min

Amortized analysis example

aggregate analysis of dynamic tables

Screencast Suthers 16 min

CLRS 17 - Amortized analysis

aggregate analysis, the accounting method, the potential method, dynamic tables

Textbook 30 pages

Notes on amortized analysis

The general idea, multipop example, aggregate analysis, accounting method, potential method, dynamic tables.

Notes