next up previous
Next: 4.6.1 Example of Sorting Up: 4. Binary Trees Previous: 4.5.1 Search, Insert, Delete in Bottom-up Splaying

4.6 Amortized Algorithm Analysis

Amortized analysis considers a long sequence of related events rather than a single event in isolation. Amortized analysis gives a worst case estimate of the cost of a long sequence of related events.