amortized analysis - analyze running time - not new algorithms, just a different way to analyze them - toy, pedagogical methods: accounting, aggregation, - real practical method: potential function - toy examples : counter, stacks real/complicated examples: - fibonacci heaps - move-to-front caching for linked lists