Module: Amortized analysis

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

Learning Outcomes

Use of the accounting method to determine the amortized cost per operation for an algorithm.

Aggregate, accounting, and potential methods

Screencast Suthers 23 min

aggregate analysis of dynamic tables

Screencast Suthers 16 min

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

Textbook 30 pages

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

Notes