McGraw-Hill OnlineMcGraw-Hill Higher EducationLearning Center
Student Center | Instructor's Center | Introduction to Algorithms | Home
Glossary A-B
Glossary B-D
Glossary D-F
Glossary F-J
Glossary J-M
Glossary M-O
Glossary O-P
Glossary P-S
Glossary S-T
Glossary T-Z
Chapter Objectives
Chapter Overview
Glossary
PowerPoint Slides
Algorithm Pseudocode
Feedback
Help Center


small text cover image
Introduction to Algorithms, 2/e
Thomas H. Cormen, Dartmouth College
Charles E. Leiserson, Massachusetts Institute of Technology
Ronald L. Rivest, Massachusetts Institute of Technology
Clifford Stein, Columbia University
Amortized Analysis

Chapter Objectives

Amortized analysis
• Analyze a sequence of operations on a data structure.
• Goal: Show that although some individual operations may be expensive, on
average the cost per operation is small.
Average in this context does not mean that we’re averaging over a distribution of
inputs.
• No probability is involved.
• We’re talking about average cost in the worst case.
Organization
We’ll look at 3 methods:
• aggregate analysis
• accounting method
• potential method
Using 3 examples:
• stack with multipop operation
• binary counter
• dynamic tables (later on)









Copyright2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.